Given a string str, the task is to split the string into minimum parts such that each part is of same length and each part is a palindrome. Print the required number of parts.
Examples:
Input: str = “civicbob”
Output: 8
“b”, “b”, “c”, “c”, “i”, “i”, “v” and “o” are the required partitions. “civic” and “bob” are also palindromes but they are not of equal lengthInput: str = “noonpeep”
Output: 1
Approach:
- Count the number of odd appearing characters and store it in countOdd.
- Sum the frequencies of all the even occurring characters and store it in sumEven.
- Since, no more than one odd frequency character can be a part of the same palindrome. So, if (sumEven / 2) % countOdd = 0 then the answer is countOdd as sumEven can be divided into countOdd parts.
- Else, we can still divide the odd occurring characters into the palindrome pairs. For example, if the character a appears 3 times i.e. aaa then aa can be a part of some palindrome while leaving a as odd (without affecting the original frequency).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h>using namespace std;// Function to return the frequency array // for the given string int* getFrequencies(string str) { static int freq[26] = { 0 }; for (int i = 0; i < str.length(); i++) { freq[str[i] - 'a']++; } return freq; } // Function to return the required count int countMinParts(string str) { int n = str.length(); int *freq = getFrequencies(str); vector<int> oddFreq, evenFreq; int i, sumEven = 0; for (i = 0; i < 26; i++) { if (freq[i] == 0) continue; // Add frequencies of the even appearing // characters if (freq[i] % 2 == 0) evenFreq.push_back(freq[i]); // Count of the characters that appeared // odd number of times else oddFreq.push_back(freq[i]); } for (i = 0; i < evenFreq.size(); i++) { sumEven += evenFreq[i]; } // If there are no characters with odd frequency if (oddFreq.size() == 0) return 1; // If there are no characters with even frequency if (sumEven == 0) { // Only a single character with odd frequency if (oddFreq.size() == 1) return 1; // More than 1 character with odd frequency // string isn't a palindrome return 0; } i = 0; // All odd appearing characters can also contribute to // the even length palindrome if one character // is removed from the frequency leaving it as even while (i < oddFreq.size()) { // If k palindromes are possible where k // is the number of characters with odd frequency if ((sumEven / 2) % oddFreq.size() == 0) return oddFreq.size(); // Current character can no longer be an element // in a string other than the mid character if (oddFreq[i] == 1) { i++; continue; } // If current character has odd frequency > 1 // take two characters which can be used in // any of the parts sumEven += 2; // Update the frequency oddFreq[i] = oddFreq[i] - 2; } // If not possible, then every character of the // string will act as a separate palindrome return n; } // Driver code int main() { string s = "noonpeep"; cout<<countMinParts(s); } |
Java
// Java implementation of the approachimport java.util.*;public class GFG { // Function to return the frequency array // for the given string static int[] getFrequencies(String str) { int freq[] = new int[26]; for (int i = 0; i < str.length(); i++) { freq[str.charAt(i) - 'a']++; } return freq; } // Function to return the required count static int countMinParts(String str) { int n = str.length(); int freq[] = getFrequencies(str); List<Integer> oddFreq = new ArrayList<>(); List<Integer> evenFreq = new ArrayList<>(); int i, sumEven = 0; for (i = 0; i < 26; i++) { if (freq[i] == 0) continue; // Add frequencies of the even appearing // characters if (freq[i] % 2 == 0) evenFreq.add(freq[i]); // Count of the characters that appeared // odd number of times else oddFreq.add(freq[i]); } for (i = 0; i < evenFreq.size(); i++) { sumEven += evenFreq.get(i); } // If there are no characters with odd frequency if (oddFreq.size() == 0) return 1; // If there are no characters with even frequency if (sumEven == 0) { // Only a single character with odd frequency if (oddFreq.size() == 1) return 1; // More than 1 character with odd frequency // string isn't a palindrome return 0; } i = 0; // All odd appearing characters can also contribute to // the even length palindrome if one character // is removed from the frequency leaving it as even while (i < oddFreq.size()) { // If k palindromes are possible where k // is the number of characters with odd frequency if ((sumEven / 2) % oddFreq.size() == 0) return oddFreq.size(); // Current character can no longer be an element // in a string other than the mid character if (oddFreq.get(i) == 1) { i++; continue; } // If current character has odd frequency > 1 // take two characters which can be used in // any of the parts sumEven += 2; // Update the frequency oddFreq.set(i, oddFreq.get(i) - 2); } // If not possible, then every character of the // string will act as a separate palindrome return n; } // Driver code public static void main(String[] args) { String s = "noonpeep"; System.out.println(countMinParts(s)); }}// This code is contributed by chitranayal |
Python3
# Python3 implementation of the approach # Function to return the frequency array # for the given string def getFrequencies(string) : freq = [0] * 26 for i in range(len(string)) : freq[ord(string[i]) - ord('a')] += 1 return freq# Function to return the required count def countMinParts(string) : n = len(string) freq = getFrequencies(string) oddFreq = [] evenFreq = [] sumEven = 0 for i in range(26) : if freq[i] == 0 : continue # Add frequencies of the even # appearing characters if freq[i] % 2 == 0 : evenFreq.append(freq[i]) # Count of the characters that # appeared odd number of times else : oddFreq.append(freq[i]) for i in range(len(evenFreq)) : sumEven += evenFreq[i] # If there are no characters with # odd frequency if len(oddFreq) == 0 : return 1 # If there are no characters with # even frequency if sumEven == 0 : # Only a single character with # odd frequency if len(oddFreq) == 1: return 1 # More than 1 character with odd # frequency string isn't a palindrome return 0 i = 0 # All odd appearing characters can also # contribute to the even length palindrome # if one character is removed from the # frequency leaving it as even while(i < len(oddFreq)) : # If k palindromes are possible where # k is the number of characters with # odd frequency if ((sumEven / 2) % len(oddFreq) == 0) : return len(oddFreq) # Current character can no longer be # an element in a string other than # the mid character if (oddFreq[i] == 1) : i += 1 continue # If current character has odd frequency > 1 # take two characters which can be used in # any of the parts sumEven += 2 # Update the frequency oddFreq[i] = oddFreq[i] - 2 # If not possible, then every character of the # string will act as a separate palindrome return n# Driver codeif __name__ == "__main__" : s = "noonpeep" print(countMinParts(s))# This code is contributed by Ryuga |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG{ // Function to return the frequency array // for the given string static int[] getFrequencies(String str) { int []freq = new int[26]; for (int i = 0; i < str.Length; i++) { freq[str[i] - 'a']++; } return freq; } // Function to return the required count static int countMinParts(String str) { int n = str.Length; int []freq = getFrequencies(str); List<int> oddFreq = new List<int>(); List<int> evenFreq = new List<int>(); int i, sumEven = 0; for (i = 0; i < 26; i++) { if (freq[i] == 0) continue; // Add frequencies of the even appearing // characters if (freq[i] % 2 == 0) evenFreq.Add(freq[i]); // Count of the characters that appeared // odd number of times else oddFreq.Add(freq[i]); } for (i = 0; i < evenFreq.Count; i++) { sumEven += evenFreq[i]; } // If there are no characters with odd frequency if (oddFreq.Count == 0) return 1; // If there are no characters with even frequency if (sumEven == 0) { // Only a single character with odd frequency if (oddFreq.Count == 1) return 1; // More than 1 character with odd frequency // string isn't a palindrome return 0; } i = 0; // All odd appearing characters can also contribute to // the even length palindrome if one character // is removed from the frequency leaving it as even while (i < oddFreq.Count) { // If k palindromes are possible where k // is the number of characters with odd frequency if ((sumEven / 2) % oddFreq.Count == 0) return oddFreq.Count; // Current character can no longer be an element // in a string other than the mid character if (oddFreq[i] == 1) { i++; continue; } // If current character has odd frequency > 1 // take two characters which can be used in // any of the parts sumEven += 2; // Update the frequency oddFreq.Insert(i, oddFreq[i] - 2); } // If not possible, then every character of the // string will act as a separate palindrome return n; } // Driver code public static void Main(String[] args) { String s = "noonpeep"; Console.WriteLine(countMinParts(s)); }}// This code has been contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approach// Function to return the frequency array // for the given stringfunction getFrequencies(str){ let freq = new Array(26); for(let i=0;i<26;i++) freq[i]=0; for (let i = 0; i < str.length; i++) { freq[str[i].charCodeAt(0) - 'a'.charCodeAt(0)]++; } return freq;}// Function to return the required countfunction countMinParts(str){ let n = str.length; let freq = getFrequencies(str); let oddFreq = []; let evenFreq = []; let i, sumEven = 0; for (i = 0; i < 26; i++) { if (freq[i] == 0) continue; // Add frequencies of the even appearing // characters if (freq[i] % 2 == 0) evenFreq.push(freq[i]); // Count of the characters that appeared // odd number of times else oddFreq.push(freq[i]); } for (i = 0; i < evenFreq.length; i++) { sumEven += evenFreq[i]; } // If there are no characters with odd frequency if (oddFreq.length == 0) return 1; // If there are no characters with even frequency if (sumEven == 0) { // Only a single character with odd frequency if (oddFreq.length == 1) return 1; // More than 1 character with odd frequency // string isn't a palindrome return 0; } i = 0; // All odd appearing characters can also contribute to // the even length palindrome if one character // is removed from the frequency leaving it as even while (i < oddFreq.length) { // If k palindromes are possible where k // is the number of characters with odd frequency if ((sumEven / 2) % oddFreq.length == 0) return oddFreq.length; // Current character can no longer be an element // in a string other than the mid character if (oddFreq[i] == 1) { i++; continue; } // If current character has odd frequency > 1 // take two characters which can be used in // any of the parts sumEven += 2; // Update the frequency oddFreq[i]= oddFreq[i] - 2; } // If not possible, then every character of the // string will act as a separate palindrome return n;} // Driver codelet s = "noonpeep";document.write(countMinParts(s));// This code is contributed by rag2127</script> |
Output
1
Time complexity: O(n) where n is the length of the given string
Auxiliary space: O(1)
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!
