Given a string S of size N and an integer K, the task is to find whether the characters of the string can be arranged to make K palindromic strings simultaneously.
Examples:
Input: S = “annabelle”, K = 2
Output: Yes
Explanation:
All characters of string S can be distributed into “elble” and “anna” which are both palindromic.
Input: S =”abcd”, K = 4
Output: Yes
Explanation:
Partition all characters of string as single character.
Approach
- If the frequency of every character is even and K lies between 1 and N then it is always possible to form K palindrome strings.
- But if there are some characters (say odd_count) with odd frequency, then K must lie between odd_count and N for K palindromic strings to be possible.
Hence, follow the steps below to solve the problem:
If K exceeds the length of the string, straightaway print “No”.
- Store the frequency of all characters in a Map.
- Count the number of characters having an odd frequency.
- If the count is less than given K, then print “No”. Otherwise, print “Yes”.
Below is the implementation of the above approach:
C++
// 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<char, 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<char, 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
// 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 Codepublic 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
# 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#
// 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 Codepublic 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 |
Javascript
<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> |
Output
Yes
Time Complexity: O (N).
Auxiliary Space: O (N).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
