Split a string in equal parts such that all parts are palindromes | 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
def getFrequencies ( string ) : NEW_LINE INDENT freq = [ 0 ] * 26 NEW_LINE for i in range ( len ( string ) ) : NEW_LINE INDENT freq [ ord ( string [ i ] ) - ord ( ' a ' ) ] += 1 NEW_LINE DEDENT return freq NEW_LINE DEDENT def countMinParts ( string ) : NEW_LINE INDENT n = len ( string ) NEW_LINE freq = getFrequencies ( string ) NEW_LINE oddFreq = [ ] NEW_LINE evenFreq = [ ] NEW_LINE sumEven = 0 NEW_LINE for i in range ( 26 ) : NEW_LINE INDENT if freq [ i ] == 0 : NEW_LINE INDENT continue NEW_LINE DEDENT if freq [ i ] % 2 == 0 : NEW_LINE INDENT evenFreq . append ( freq [ i ] ) NEW_LINE DEDENT else : NEW_LINE INDENT oddFreq . append ( freq [ i ] ) NEW_LINE DEDENT DEDENT for i in range ( len ( evenFreq ) ) : NEW_LINE INDENT sumEven += evenFreq [ i ] NEW_LINE DEDENT if len ( oddFreq ) == 0 : NEW_LINE INDENT return 1 NEW_LINE DEDENT if sumEven == 0 : NEW_LINE INDENT if len ( oddFreq ) == 1 : NEW_LINE INDENT return 1 NEW_LINE DEDENT return 0 NEW_LINE DEDENT i = 0 NEW_LINE while ( i < len ( oddFreq ) ) : NEW_LINE INDENT if ( ( sumEven / 2 ) % len ( oddFreq ) == 0 ) : NEW_LINE INDENT return len ( oddFreq ) NEW_LINE DEDENT if ( oddFreq [ i ] == 1 ) : NEW_LINE INDENT i += 1 NEW_LINE continue NEW_LINE DEDENT sumEven += 2 NEW_LINE oddFreq [ i ] = oddFreq [ i ] - 2 NEW_LINE DEDENT return n NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " noonpeep " NEW_LINE print ( countMinParts ( s ) ) NEW_LINE DEDENT