Encuentra si la string es K-Palindrome o no usa todos los caracteres exactamente una vez

Dada una string str y un entero K , la tarea es verificar si es posible hacer palíndromos de la string K usando todos los caracteres de la string exactamente una vez.
Ejemplos: 
 

Entrada: str = «pobre», K = 3 
Salida: Sí 
Una forma de obtener 3 palíndromos es: oo, p, r
Entrada: str = «divertido», K = 5 
Salida: No No 
se pueden construir 2 palíndromos usando 3 letras distintas. Por lo tanto no es posible. 
 

Acercarse: 
 

  1. Si el tamaño de la string es menor que k, no es posible obtener k palíndromos.
  2. Si el tamaño de la string es igual a k, siempre es posible obtener k palíndromos. Damos 1 carácter a cada una de las k strings y todas ellas son palíndromos ya que una string de longitud 1 siempre es un palíndromo.
  3. Si el tamaño de la string es mayor que k, algunas strings pueden tener más de 1 carácter. 
    • Cree un hashmap para almacenar la frecuencia de cada carácter, ya que los caracteres que tienen un número par de ocurrencias se pueden distribuir en grupos de 2.
    • Comprueba si el número de caracteres que tienen un número impar de ocurrencias es menor o igual que k, podemos decir que siempre se pueden generar k palíndromos, de lo contrario no.

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program to find if string is K-Palindrome
// or not using all characters exactly once
 
#include <bits/stdc++.h>
using namespace std;
 
void iskPalindromesPossible(string s, int k)
{
    // when size of string is less than k
    if (s.size() < k) {
        cout << "Not Possible" << endl;
        return;
    }
 
    // when size of string is equal to k
    if (s.size() == k) {
        cout << "Possible" << endl;
        return;
    }
 
    // when size of string is greater than k
 
    // to store the frequencies of the characters
    map<char, int> freq;
    for (int i = 0; i < s.size(); i++)
        freq[s[i]]++;
 
    // to store the count of characters
    // whose number of occurrences is odd.
    int count = 0;
 
    // iterating over the map
    for (auto it : freq) {
        if (it.second % 2 == 1)
            count++;
    }
    if (count > k)
        cout << "No" << endl;
    else
        cout << "Yes" << endl;
}
 
// Driver code
int main()
{
 
    string str = "poor";
    int K = 3;
    iskPalindromesPossible(str, K);
 
    str = "geeksforgeeks";
    K = 10;
    iskPalindromesPossible(str, K);
 
    return 0;
}

Java

// Java program to find if String
// is K-Palindrome or not using
// all characters exactly once
import java.util.*;
 
class GFG{
 
static void iskPalindromesPossible(String s,
                                   int k)
{
     
    // When size of String is less than k
    if (s.length() < k)
    {
        System.out.print("Not Possible" + "\n");
        return;
    }
 
    // When size of String is equal to k
    if (s.length() == k)
    {
        System.out.print("Possible" + "\n");
        return;
    }
     
    // When size of String is greater than k
    // to store the frequencies of the characters
    HashMap<Character,
            Integer> freq = new HashMap<Character,
                                        Integer>();
    for(int i = 0; i < s.length(); i++)
       if(freq.containsKey(s.charAt(i)))
       {
           freq.put(s.charAt(i),
           freq.get(s.charAt(i)) + 1);
       }
       else
       {
           freq.put(s.charAt(i), 1);
       }
 
    // To store the count of characters
    // whose number of occurrences is odd.
    int count = 0;
 
    // Iterating over the map
    for(Map.Entry<Character,
                  Integer> it : freq.entrySet())
    {
       if (it.getValue() % 2 == 1)
           count++;
    }
     
    if (count > k)
        System.out.print("No" + "\n");
    else
        System.out.print("Yes" + "\n");
}
 
// Driver code
public static void main(String[] args)
{
    String str = "poor";
    int K = 3;
    iskPalindromesPossible(str, K);
 
    str = "geeksforgeeks";
    K = 10;
    iskPalindromesPossible(str, K);
}
}
 
// This code is contributed by sapnasingh4991

Python3

# Find if string is K-Palindrome or not using all characters exactly once
# Python 3 program to find if string is K-Palindrome
# or not using all characters exactly once
 
def iskPalindromesPossible(s, k):
 
    # when size of string is less than k
    if (len(s)<k):
        print("Not Possible")
        return
 
    # when size of string is equal to k
    if (len(s) == k):
        print("Possible")
        return
 
    # when size of string is greater than k
 
    # to store the frequencies of the characters
    freq = dict.fromkeys(s,0)
    for i in range(len(s)):
        freq[s[i]] += 1
 
    #to store the count of characters
    # whose number of occurrences is odd.
    count = 0
 
    # iterating over the map
    for value in freq.values():
        if (value % 2 == 1):
            count += 1
    if (count > k):
        print("No")
    else:
        print("Yes")
 
# Driver code
if __name__ == '__main__':
    str1 = "poor"
    K = 3
    iskPalindromesPossible(str1, K)
 
    str = "geeksforgeeks"
    K = 10
    iskPalindromesPossible(str, K)
 
# This code is contributed by Surendra_Gangwar

C#

// C# program to find if String
// is K-Palindrome or not using
// all characters exactly once
using System;
using System.Collections.Generic;
 
class GFG{
 
static void iskPalindromesPossible(String s,
                                   int k)
{
     
    // When size of String is less than k
    if (s.Length < k)
    {
        Console.Write("Not Possible" + "\n");
        return;
    }
 
    // When size of String is equal to k
    if (s.Length == k)
    {
        Console.Write("Possible" + "\n");
        return;
    }
     
    // When size of String is greater than k
    // to store the frequencies of the characters
    Dictionary<int,
               int> freq = new Dictionary<int,
                                          int>();
    for(int i = 0; i < s.Length; i++)
        if(freq.ContainsKey(s[i]))
        {
            freq[s[i]] = freq[s[i]] + 1;
        }
        else
        {
            freq.Add(s[i], 1);
        }
 
    // To store the count of characters
    // whose number of occurrences is odd.
    int count = 0;
 
    // Iterating over the map
    foreach(KeyValuePair<int, int> it in freq)
    {
        if (it.Value % 2 == 1)
            count++;
    }
     
    if (count > k)
        Console.Write("No" + "\n");
    else
        Console.Write("Yes" + "\n");
}
 
// Driver code
public static void Main(String[] args)
{
    String str = "poor";
    int K = 3;
    iskPalindromesPossible(str, K);
 
    str = "geeksforgeeks";
    K = 10;
    iskPalindromesPossible(str, K);
}
}
 
// This code is contributed by Princi Singh

Javascript

<Script>
 
// Find if string is K-Palindrome or not using all characters exactly once
// JavaScript program to find if string is K-Palindrome
// or not using all characters exactly once
function iskPalindromesPossible(s, k)
{
 
    // when size of string is less than k
    if (s.length < k)
    {
        document.write("Not Possible","</br>")
        return
    }
 
    // when size of string is equal to k
    if (s.length == k){
        document.write("Possible","</br>")
        return
    }
 
    // when size of string is greater than k
 
    // to store the frequencies of the characters
    let freq = new Map()
    for(let i = 0; i < s.length; i++)
    {
        if(freq.has(s[i])){
            freq.set(s[i],freq.get(s[i])+1);
        }
        freq.set(s[i],1);
    }
    // to store the count of characters
    // whose number of occurrences is odd.
    let count = 0
 
    // iterating over the map
    for(let [key,value] of freq){
        if (value % 2 == 1)
            count += 1
    }
    if (count > k)
        document.write("No","</br>")
    else
        document.write("Yes","</br>")
}
 
// Driver code
 
let str1 = "poor"
let K = 3
iskPalindromesPossible(str1, K)
 
let str = "geeksforgeeks"
K = 10
iskPalindromesPossible(str, K)
 
// This code is contributed by shinjanpatra
 
</script>
Producción: 

Yes
Yes

 

Publicación traducida automáticamente

Artículo escrito por aqibmahboob1999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *