Given a string S, the task is to divide the characters of S to form minimum number of palindromic strings.
Note: There can be multiple correct answers.
Examples:
Input: S = “neveropen”
Output: {eegksrskgee, o, f}Explanation:
There should be at least 3 strings “eegksrskgee”, “o”, “f”. All 3 formed strings are palindrome.Input: S = “abbaa”
Output: {“ababa”}Explanation:
The given string S = “ababa” is already a palindrome string so, only 1 string will be formed.Input: S = “abc”
Output: {“a”, “b”, “c”}Explanation:
There should be at least 3 strings “a”, “b”, “c”. All 3 formed strings are palindrome.
Approach:
The main observation is that a palindrome string remains the same if reversed. The length of the strings formed does not matter so try to make a string as large as possible. If some character can’t be a part of palindromic string, then push this character into a new string.
- The general approach would be to store the frequency of each character and if for some character the frequency is odd then we have to make a new string and increment our answer by 1.
- Note that if there are no characters with odd frequency, at least one string is still needed, so the final answer will be max(1, odd frequency characters).
- To print the string store odd characters frequency characters in a vector and even characters in another vector.
- Form one palindromic string with strings having odd characters and append a string with an even number of characters and all other strings will be of only one character.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to return// minimum palindromic strings formedint minimumPalindromicStrings(string S){ // Store the length of string int N = S.length(); // Iterate over the string // and store the frequency of // all characters A vector // to store the frequency vector<int> freq(26); for (int i = 0; i < N; i++) { freq[S[i] - 'a']++; } // Store the odd frequency characters vector<int> oddFreqCharacters; // Store the even frequency of characters // in the same vector by dividing // current frequency by 2 as one element // will be used on left as well as right side // Iterate through all possible characters // and check the parity of frequency for (int i = 0; i < 26; i++) { if (freq[i] & 1) { oddFreqCharacters.push_back(i); freq[i]--; } freq[i] /= 2; } // store answer in a vector vector<string> ans; // if there are no odd Frequency characters // then print the string with even characters if (oddFreqCharacters.empty()) { // store the left part // of the palindromic string string left = ""; for (int i = 0; i < 26; i++) { for (int j = 0; j < freq[i]; j++) { left += char(i + 'a'); } } string right = left; // reverse the right part of the string reverse(right.begin(), right.end()); // store the string in ans vector ans.push_back(left + right); } else { // take any character // from off frequency element string middle = ""; int c = oddFreqCharacters.back(); oddFreqCharacters.pop_back(); middle += char(c + 'a'); // repeat the above step to form // left and right strings string left = ""; for (int i = 0; i < 26; i++) { for (int j = 0; j < freq[i]; j++) { left += char(i + 'a'); } } string right = left; // reverse the right part of the string reverse(right.begin(), right.end()); // store the string in ans vector ans.push_back(left + middle + right); // store all other odd frequency strings while (!oddFreqCharacters.empty()) { int c = oddFreqCharacters.back(); oddFreqCharacters.pop_back(); string middle = ""; middle += char(c + 'a'); ans.push_back(middle); } } // Print the answer cout << "["; for (int i = 0; i < ans.size(); i++) { cout << ans[i]; if (i != ans.size() - 1) { cout << ", "; } } cout << "]"; return 0;}// Driver Codeint main(){ string S = "neveropen"; minimumPalindromicStrings(S);} |
Java
// Java Program to implement// the above approachimport java.util.*;class GFG{// Function to return// minimum palindromic Strings formedstatic int minimumPalindromicStrings(String S){ // Store the length of String int N = S.length(); // Iterate over the String // and store the frequency of // all characters A vector // to store the frequency int[] freq = new int[26]; for (int i = 0; i < N; i++) { freq[S.charAt(i) - 'a']++; } // Store the odd frequency characters Vector<Integer> oddFreqCharacters = new Vector<Integer>(); // Store the even frequency of characters // in the same vector by dividing // current frequency by 2 as one element // will be used on left as well as right side // Iterate through all possible characters // and check the parity of frequency for (int i = 0; i < 26; i++) { if (freq[i] % 2 == 1) { oddFreqCharacters.add(i); freq[i]--; } freq[i] /= 2; } // store answer in a vector Vector<String> ans = new Vector<String>(); // if there are no odd Frequency characters // then print the String with even characters if (oddFreqCharacters.isEmpty()) { // store the left part // of the palindromic String String left = ""; for (int i = 0; i < 26; i++) { for (int j = 0; j < freq[i]; j++) { left += (char)(i + 'a'); } } String right = left; // reverse the right part of the String right = reverse(right); // store the String in ans vector ans.add(left + right); } else { // take any character // from off frequency element String middle = ""; int c = oddFreqCharacters.lastElement(); oddFreqCharacters.remove(oddFreqCharacters.size()-1); middle += (char)(c + 'a'); // repeat the above step to form // left and right Strings String left = ""; for (int i = 0; i < 26; i++) { for (int j = 0; j < freq[i]; j++) { left += (char)(i + 'a'); } } String right = left; // reverse the right part of the String right = reverse(right); // store the String in ans vector ans.add(left + middle + right); // store all other odd frequency Strings while (!oddFreqCharacters.isEmpty()) { c = oddFreqCharacters.lastElement(); oddFreqCharacters.remove(oddFreqCharacters.size()-1); middle = ""; middle += (char)(c + 'a'); ans.add(middle); } } // Print the answer System.out.print("["); for (int i = 0; i < ans.size(); i++) { System.out.print(ans.get(i)); if (i != ans.size() - 1) { System.out.print(", "); } } System.out.print("]"); return 0;}static String reverse(String input) { char[] a = input.toCharArray(); int l, r = a.length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.valueOf(a);} // Driver Codepublic static void main(String[] args){ String S = "neveropen"; minimumPalindromicStrings(S);}}// This code is contributed by 29AjayKumar |
Python3
def minimum_palindromic_strings(s): # Store the length of the string n = len(s) # Iterate over the string and store the frequency of all characters in a dictionary freq = {} for char in s: if char in freq: freq[char] += 1 else: freq[char] = 1 # Store the odd frequency characters odd_freq_characters = [] # Store the even frequency of characters in the same dictionary # by dividing current frequency by 2 # as one element will be used on the left as well as the right side # Iterate through all possible characters and check the parity of frequency for char in freq: if freq[char] % 2 == 1: odd_freq_characters.append(char) freq[char] -= 1 freq[char] //= 2 # Store answers in a list ans = [] # If there are no odd frequency characters, then print the string with even characters if not odd_freq_characters: # Store the left part of the palindromic string left = "" for char in sorted(freq): left += char * freq[char] right = left[::-1] # Reverse the right part of the string # Store the string in the ans list ans.append(left + right) else: # Take any character from off-frequency elements middle = odd_freq_characters.pop() middle = middle # Repeat the above step to form left and right strings left = "" for char in sorted(freq): left += char * freq[char] right = left[::-1] # Reverse the right part of the string # Store the string in the ans list ans.append(left + middle + right) # Store all other odd frequency strings for char in odd_freq_characters: ans.append(char) # Print the answer print(ans)# Driver Codeif __name__ == "__main__": S = "neveropen" minimum_palindromic_strings(S) |
C#
// C# Program to implement// the above approachusing System;using System.Collections.Generic;public class GFG{// Function to return// minimum palindromic Strings formedstatic int minimumPalindromicStrings(String S){ // Store the length of String int N = S.Length; // Iterate over the String // and store the frequency of // all characters A vector // to store the frequency int[] freq = new int[26]; for (int i = 0; i < N; i++) { freq[S[i] - 'a']++; } // Store the odd frequency characters List<int> oddFreqchars = new List<int>(); // Store the even frequency of characters // in the same vector by dividing // current frequency by 2 as one element // will be used on left as well as right side // Iterate through all possible characters // and check the parity of frequency for (int i = 0; i < 26; i++) { if (freq[i] % 2 == 1) { oddFreqchars.Add(i); freq[i]--; } freq[i] /= 2; } // store answer in a vector List<String> ans = new List<String>(); // if there are no odd Frequency characters // then print the String with even characters if (oddFreqchars.Count==0) { // store the left part // of the palindromic String String left = ""; for (int i = 0; i < 26; i++) { for (int j = 0; j < freq[i]; j++) { left += (char)(i + 'a'); } } String right = left; // reverse the right part of the String right = reverse(right); // store the String in ans vector ans.Add(left + right); } else { // take any character // from off frequency element String middle = ""; int c = oddFreqchars[oddFreqchars.Count-1]; oddFreqchars.RemoveAt(oddFreqchars.Count-1); middle += (char)(c + 'a'); // repeat the above step to form // left and right Strings String left = ""; for (int i = 0; i < 26; i++) { for (int j = 0; j < freq[i]; j++) { left += (char)(i + 'a'); } } String right = left; // reverse the right part of the String right = reverse(right); // store the String in ans vector ans.Add(left + middle + right); // store all other odd frequency Strings while (oddFreqchars.Count!=0) { c = oddFreqchars[oddFreqchars.Count-1]; oddFreqchars.RemoveAt(oddFreqchars.Count-1); middle = ""; middle += (char)(c + 'a'); ans.Add(middle); } } // Print the answer Console.Write("["); for (int i = 0; i < ans.Count; i++) { Console.Write(ans[i]); if (i != ans.Count - 1) { Console.Write(", "); } } Console.Write("]"); return 0;}static String reverse(String input) { char[] a = input.ToCharArray(); int l, r = a.Length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.Join("",a);} // Driver Codepublic static void Main(String[] args){ String S = "neveropen"; minimumPalindromicStrings(S);}} // This code is contributed by 29AjayKumar |
Javascript
function minimumPalindromicStrings(S) { // Store the length of the string const N = S.length; // Iterate over the string and store the frequency of all characters in an array const freq = new Array(26).fill(0); for (let i = 0; i < N; i++) { freq[S.charCodeAt(i) - 'a'.charCodeAt(0)]++; } // Store the odd frequency characters const oddFreqCharacters = []; // Iterate through all possible characters and check the parity of frequency for (let i = 0; i < 26; i++) { if (freq[i] & 1) { oddFreqCharacters.push(i); freq[i]--; } freq[i] /= 2; } // Store answers in an array const ans = []; // If there are no odd frequency characters, then print the string with even characters if (oddFreqCharacters.length === 0) { // Store the left part of the palindromic string let left = ""; for (let i = 0; i < 26; i++) { for (let j = 0; j < freq[i]; j++) { left += String.fromCharCode(i + 'a'.charCodeAt(0)); } } const right = left.split("").reverse().join(""); // Reverse the right part of the string // Store the string in the ans array ans.push(left + right); } else { // Take any character from off-frequency elements let middle = ""; const c = oddFreqCharacters.pop(); middle += String.fromCharCode(c + 'a'.charCodeAt(0)); // Repeat the above step to form left and right strings let left = ""; for (let i = 0; i < 26; i++) { for (let j = 0; j < freq[i]; j++) { left += String.fromCharCode(i + 'a'.charCodeAt(0)); } } const right = left.split("").reverse().join(""); // Reverse the right part of the string // Store the string in the ans array ans.push(left + middle + right); // Store all other odd frequency strings while (oddFreqCharacters.length > 0) { const c = oddFreqCharacters.pop(); let middle = ""; middle += String.fromCharCode(c + 'a'.charCodeAt(0)); ans.push(middle); } } // Print the answer console.log(ans);}// Driver Codeconst S = "neveropen";minimumPalindromicStrings(S); |
Output
[eegksrskgee, o, f]
Time Complexity: O(N*26)
Space Complexity: 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!
