Split a string in equal parts such that all parts are palindromes | C ++ implementation of the approach ; Function to return the frequency array for the given string ; Function to return the required count ; Add frequencies of the even appearing characters ; Count of the characters that appeared odd number of times ; If there are no characters with odd frequency ; If there are no characters with even frequency ; Only a single character with odd frequency ; More than 1 character with odd frequency string isn 't a palindrome ; All odd appearing characters can also contribute to the even length palindrome if one character is removed from the frequency leaving it as even ; If k palindromes are possible where k is the number of characters with odd frequency ; Current character can no longer be an element in a string other than the mid character ; If current character has odd frequency > 1 take two characters which can be used in any of the parts ; Update the frequency ; If not possible , then every character of the string will act as a separate palindrome ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int * getFrequencies ( string str ) { static int freq [ 26 ] = { 0 } ; for ( int i = 0 ; i < str . length ( ) ; i ++ ) { freq [ str [ i ] - ' a ' ] ++ ; } return freq ; } 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 ; if ( freq [ i ] % 2 == 0 ) evenFreq . push_back ( freq [ i ] ) ; else oddFreq . push_back ( freq [ i ] ) ; } for ( i = 0 ; i < evenFreq . size ( ) ; i ++ ) { sumEven += evenFreq [ i ] ; } if ( oddFreq . size ( ) == 0 ) return 1 ; if ( sumEven == 0 ) { if ( oddFreq . size ( ) == 1 ) return 1 ; return 0 ; } i = 0 ; while ( i < oddFreq . size ( ) ) { if ( ( sumEven / 2 ) % oddFreq . size ( ) == 0 ) return oddFreq . size ( ) ; if ( oddFreq [ i ] == 1 ) { i ++ ; continue ; } sumEven += 2 ; oddFreq [ i ] = oddFreq [ i ] - 2 ; } return n ; } int main ( ) { string s = " noonpeep " ; cout << countMinParts ( s ) ; }