Comprobar si se pueden formar K strings palindrómicas a partir de una string dada

Dada una string S de tamaño N y un número entero K , la tarea es encontrar si los caracteres de la string pueden organizarse para formar K strings palindrómicas simultáneamente. 
Ejemplos:

Entrada: S = «annabelle», K = 2 
Salida: Sí 
Explicación: 
Todos los caracteres de la string S se pueden distribuir en «elble» y «anna», que son palindrómicos.
Entrada: S =”abcd”, K = 4 
Salida: Sí 
Explicación: 
Divida todos los caracteres de la string como un solo carácter.

Acercarse

• Si la frecuencia de cada carácter es par y K se encuentra entre 1 y N, siempre es posible formar strings de palíndromos K.
• Pero si hay algunos caracteres (por ejemplo, odd_count ) con una frecuencia impar, entonces K debe estar entre odd_count y N para que sean posibles las K strings palindrómicas.

Por lo tanto, siga los pasos a continuación para resolver el problema:

Si K excede la longitud de la string, imprima inmediatamente «No» .  

1. Almacena la frecuencia de todos los caracteres en un Mapa .
2. Cuente el número de caracteres que tienen una frecuencia impar.
3. Si el conteo es menor que K dado, imprima «No». De lo contrario, escriba «Sí».

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

// C++ program to check
// whether the string is
// K palindrome or not
#include <iostream>
#include <map>
using namespace std;
 
// function to check
// whether the string is
// K palindrome or not
bool can_Construct(string S, int K)
{
    // map to frequency of character
    map<int, int> m;
 
    int i = 0, j = 0, p = 0;
 
    // Check when k is given
    // as same as length of string
    if (S.length() == K) {
        return true;
    }
 
    // iterator for map
    map<int, int>::iterator h;
 
    // storing the frequency of every
    // character in map
    for (i = 0; i < S.length(); i++) {
        m[S[i]] = m[S[i]] + 1;
    }
 
    // if K is greater than size
    // of string then return false
    if (K > S.length()) {
        return false;
    }
 
    else {
 
        // check that number of character
        // having the odd frequency
        for (h = m.begin(); h != m.end(); h++) {
 
            if (m[h->first] % 2 != 0) {
                p = p + 1;
            }
        }
    }
 
    // if k is less than number of odd
    // frequency character then it is
    // again false other wise true
    if (K < p) {
        return false;
    }
 
    return true;
}
 
// Driver code
int main()
{
    string S = "annabelle";
    int K = 4;
 
    if (can_Construct(S, K)) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }
}

// Java program to check
// whether the string is
// K palindrome or not
import java.util.*;
 
class GFG{
 
// Function to check whether
// the string is K palindrome or not
static boolean can_Construct(String S, int K)
{
     
    // Map to frequency of character
    Map<Character, Integer> m = new HashMap<>();
     
    int p = 0;
     
    // Check when k is given
    // as same as length of string
    if (S.length() == K)
        return true;
     
    // Storing the frequency of every
    // character in map
    for(int i = 0; i < S.length(); i++)
        m.put(S.charAt(i),
              m.getOrDefault(S.charAt(i), 0) + 1);
               
    // If K is greater than size
    // of then return false
    if (K > S.length())
        return false;
     
    else
    {
         
        // Check that number of character
        // having the odd frequency
        for(Integer h : m.values())
        {
            if (h % 2 != 0)
                p = p + 1;
        }
    }
     
    // If k is less than number of odd
    // frequency character then it is
    // again false otherwise true
    if (K < p)
        return false;
     
    return true;
}
 
// Driver Code
public static void main (String[] args)
{
    String S = "annabelle";
    int K = 4;
     
    if (can_Construct(S, K))
        System.out.println("Yes");
    else
        System.out.println("No");
}
}
 
// This code is contributed by offbeat

# Python3 program to check whether
# the is K palindrome or not
 
# Function to check whether
# the is K palindrome or not
def can_Construct(S, K):
     
    # map to frequency of character
    m = dict()
    p = 0
     
    # Check when k is given
    # as same as length of string
    if (len(S) == K):
        return True
 
    # Storing the frequency of every
    # character in map
    for i in S:
        m[i] = m.get(i, 0) + 1
 
    # If K is greater than size
    # of then return false
    if (K > len(S)):
        return False
 
    else:
 
        # Check that number of character
        # having the odd frequency
        for h in m:
            if (m[h] % 2 != 0):
                p = p + 1
 
    # If k is less than number of odd
    # frequency character then it is
    # again false otherwise true
    if (K < p):
        return False
 
    return True
 
# Driver code
if __name__ == '__main__':
     
    S = "annabelle"
    K = 4
 
    if (can_Construct(S, K)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by mohit kumar 29

// C# program to check
// whether the string is
// K palindrome or not
using System;
using System.Collections.Generic;
class GFG{
 
// Function to check whether
// the string is K palindrome or not
static bool can_Construct(String S,
                          int K)
{    
  // Map to frequency of character
  Dictionary<char,
             int> m = new Dictionary<char,
                                     int>();
  int p = 0;
 
  // Check when k is given
  // as same as length of string
  if (S.Length == K)
    return true;
 
  // Storing the frequency of every
  // character in map
  for(int i = 0; i < S.Length; i++)
    if(!m.ContainsKey(S[i]))
      m.Add(S[i], 1);
  else
    m[S[i]] = m[S[i]] + 1;
 
  // If K is greater than size
  // of then return false
  if (K > S.Length)
    return false;
 
  else
  {
    // Check that number of character
    // having the odd frequency
    foreach(int h in m.Values)
    {
      if (h % 2 != 0)
        p = p + 1;
    }
  }
 
  // If k is less than number of odd
  // frequency character then it is
  // again false otherwise true
  if (K < p)
    return false;
 
  return true;
}
 
// Driver Code
public static void Main(String[] args)
{
  String S = "annabelle";
  int K = 4;
  if (can_Construct(S, K))
    Console.WriteLine("Yes");
  else
    Console.WriteLine("No");
}
}
 
// This code is contributed by shikhasingrajput

<script>
 
// JavaScript program to check
// whether the string is
// K palindrome or not
 
// function to check
// whether the string is
// K palindrome or not
function can_Construct(S, K)
{
    // map to frequency of character
    var m = new Map();
 
    var i = 0, j = 0, p = 0;
 
    // Check when k is given
    // as same as length of string
    if (S.length == K) {
        return true;
    }
 
 
    // storing the frequency of every
    // character in map
    for (i = 0; i < S.length; i++) {
        if(m.has(S[i]))
            m.set(S[i], m.get(S[i])+1)
        else   
            m.set(S[i], 1)
 
    }
 
    // if K is greater than size
    // of string then return false
    if (K > S.length) {
        return false;
    }
 
    else {
 
        // check that number of character
        // having the odd frequency
        m.forEach((value, key) => {
             
 
            if (value%2 != 0) {
                p = p + 1;
            }
        });
    }
 
    // if k is less than number of odd
    // frequency character then it is
    // again false other wise true
    if (K < p) {
        return false;
    }
 
    return true;
}
 
// Driver code
var S = "annabelle";
var K = 4;
if (can_Construct(S, K)) {
    document.write( "Yes");
}
else {
    document.write( "No");
}
 
 
</script>

Yes

Complejidad Temporal: O (N) . 
Espacio Auxiliar: O (N) .