Given a string str of length N, and an integer K, the task is to form K different strings by choosing characters from the given string such that all the strings formed are palindrome and the length of the smallest string among the K strings is maximum possible.
Examples:
Input: str = “qrsprtps”, K = 2
Output: 3
Explanation: The 2 strings are: “pqp” and ” rssr”.
Using 2 ‘p’ and 1 ‘q’ the 1st string is formed and using 2 ‘r’ and 2 ‘s’ the 2nd string is formed.
The 1st string is the smallest among the K strings and is of length 3 so the answer is 3.Input: str = “aaaabcbabca”, K = 3
Output: 3
Explanation: Possible 3 palindromic strings of maximum possible length are: “aba”, “aba”, “aba”.
The length of the smallest string among these is 3.
Approach: The approach is based on the Greedy technique. Try to distribute a pair of same characters to K strings equally. Make pairs of identical characters to ensure the string formed will be a palindrome. An even length palindrome of length N will have N/2 such pairs and an odd length will have an extra character along with the N/2 pairs.
- Count the frequency of the characters in the given string and the number of pairs that can be formed with those characters.
- Distribute these pairs among K strings as long as there are K pairs available. (i.e. if there are 5 such pairs and K = 2 then, distribute 2 pairs to each so that a 4 length palindromic string can be formed single pair will be left undistributed)
- Now there will be all even length palindromic strings. As the pairs left cannot be distributed among all the strings so the smallest string will have a length of twice the number of character pairs distributed to each of the strings.
- Try to add 1 more character to see if an odd length string can be formed.
- From the remaining characters i.e., the characters which were not a part of the pairs and the characters from the leftover pair of characters, add 1 character to each string to increase the maximum length by 1.
- If there are at least K such characters present then only the minimum length can be increased by one for all strings.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum possible// minimum length among the// K palindromic strings formed// from given string strint form_K_Strings(string& str, int k){ int n = str.size(); unordered_map<char, int> freq; // Storing the frequency of the characters for (auto i : str) freq[i]++; // Traversing the map to count // the number of pairs // that can be formed // and count the remaining // individual characters int pairs = 0, remChar = 0; for (auto i : freq) { pairs += (i.second / 2); if (i.second % 2 == 1) remChar++; } // Calculating the number of pairs // each string will receive // upon equally distributing. int distributed = pairs / k; // Length of these strings will be // twice of the pairs received. // This is length of the smallest string int res = distributed * 2; // If some pairs are left then // characters of the pairs can be treated // as individual remaining characters and // each pair will give 2 such characters int remPairs = pairs % k; remChar += 2 * remPairs; // If atleast k remaining characters // then we can add 1 character to // each of the strings to form // an odd length palindrome. // So now the length of the smallest // string will increase by 1. if (remChar >= k) res++; return res;}// Driver codeint main(){ string str = "qrsprtps"; int K = 2; // Function call cout << form_K_Strings(str, K); return 0;} |
Java
// JAVA code to implement the approachimport java.util.*;class GFG{ // Function to find the maximum possible // minimum length among the // K palindromic strings formed // from given string str public static int form_K_Strings(String str, int k) { int n = str.length(); HashMap<Character, Integer> freq = new HashMap<>(); // Storing the frequency of the characters char[] strArray = str.toCharArray(); for (char c : strArray) { if (freq.containsKey(c)) { freq.put(c, freq.get(c) + 1); } else { freq.put(c, 1); } } // Traversing the map to count // the number of pairs // that can be formed // and count the remaining // individual characters int pairs = 0, remChar = 0; for (Map.Entry<Character, Integer> i : freq.entrySet()) { pairs += (i.getValue() / 2); if (i.getValue() % 2 == 1) remChar++; } // Calculating the number of pairs // each string will receive // upon equally distributing. int distributed = pairs / k; // Length of these strings will be // twice of the pairs received. // This is length of the smallest string int res = distributed * 2; // If some pairs are left then // characters of the pairs can be treated // as individual remaining characters and // each pair will give 2 such characters int remPairs = pairs % k; remChar += 2 * remPairs; // If atleast k remaining characters // then we can add 1 character to // each of the strings to form // an odd length palindrome. // So now the length of the smallest // string will increase by 1. if (remChar >= k) res++; return res; } // Driver code public static void main(String[] args) { String str = "qrsprtps"; int K = 2; // Function call System.out.print(form_K_Strings(str, K)); }}// This code is contributed by Taranpreet |
Python3
# Python 3 code to implement the approachfrom collections import defaultdict# Function to find the maximum possible# minimum length among the# K palindromic strings formed# from given string strdef form_K_Strings(st, k): n = len(st) freq = defaultdict(int) # Storing the frequency of the characters for i in st: freq[i] += 1 # Traversing the map to count # the number of pairs # that can be formed # and count the remaining # individual characters pairs = 0 remChar = 0 for i in freq: pairs += (freq[i] // 2) if (freq[i] % 2 == 1): remChar += 1 # Calculating the number of pairs # each string will receive # upon equally distributing. distributed = pairs // k # Length of these strings will be # twice of the pairs received. # This is length of the smallest string res = distributed * 2 # If some pairs are left then # characters of the pairs can be treated # as individual remaining characters and # each pair will give 2 such characters remPairs = pairs % k remChar += 2 * remPairs # If atleast k remaining characters # then we can add 1 character to # each of the strings to form # an odd length palindrome. # So now the length of the smallest # string will increase by 1. if (remChar >= k): res += 1 return res# Driver codeif __name__ == "__main__": st = "qrsprtps" K = 2 # Function call print(form_K_Strings(st, K)) # This code is contributed by ukasp. |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;class GFG{ // Function to find the maximum possible // minimum length among the // K palindromic strings formed // from given string str static int form_K_Strings(string str, int k) { int n = str.Length; Dictionary<char, int> freq = new Dictionary<char, int>(); // Storing the frequency of the characters char[] strArray = str.ToCharArray(); foreach (char c in strArray) { if (!freq.ContainsKey(c)) { freq.Add(c, 1); } else { freq += 1; } } // Traversing the map to count // the number of pairs // that can be formed // and count the remaining // individual characters int pairs = 0, remChar = 0; foreach(KeyValuePair<char, int> i in freq) { pairs += (i.Value / 2); if (i.Value % 2 == 1) remChar++; } // Calculating the number of pairs // each string will receive // upon equally distributing. int distributed = pairs / k; // Length of these strings will be // twice of the pairs received. // This is length of the smallest string int res = distributed * 2; // If some pairs are left then // characters of the pairs can be treated // as individual remaining characters and // each pair will give 2 such characters int remPairs = pairs % k; remChar += 2 * remPairs; // If atleast k remaining characters // then we can add 1 character to // each of the strings to form // an odd length palindrome. // So now the length of the smallest // string will increase by 1. if (remChar >= k) res++; return res; } // Driver code public static void Main() { string str = "qrsprtps"; int K = 2; // Function call Console.Write(form_K_Strings(str, K)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find the maximum possible // minimum length among the // K palindromic strings formed // from given string str function form_K_Strings(str, k) { let n = str.length; let freq = new Map(); // Storing the frequency of the characters for (let i = 0; i < str.length; i++) { if (freq.has(str[i])) { freq.set(str[i], freq.get(str[i]) + 1) } else { freq.set(str[i], 1) } } // Traversing the map to count // the number of pairs // that can be formed // and count the remaining // individual characters let pairs = 0, remChar = 0; for (let [key, val] of freq) { pairs += Math.floor(val / 2); if (val % 2 == 1) remChar++; } // Calculating the number of pairs // each string will receive // upon equally distributing. let distributed = Math.floor(pairs / k); // Length of these strings will be // twice of the pairs received. // This is length of the smallest string let res = distributed * 2; // If some pairs are left then // characters of the pairs can be treated // as individual remaining characters and // each pair will give 2 such characters let remPairs = pairs % k; remChar += 2 * remPairs; // If atleast k remaining characters // then we can add 1 character to // each of the strings to form // an odd length palindrome. // So now the length of the smallest // string will increase by 1. if (remChar >= k) res++; return res; } // Driver code let str = "qrsprtps"; let K = 2; // Function call document.write(form_K_Strings(str, K)); // This code is contributed by Potta Lokesh </script> |
Output
3
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!
