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
using System ; using System . Collections . Generic ; class GFG { static int [ ] getFrequencies ( String str ) { int [ ] freq = new int [ 26 ] ; for ( int i = 0 ; i < str . Length ; i ++ ) { freq [ str [ i ] - ' a ' ] ++ ; } return freq ; } 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 ; if ( freq [ i ] % 2 == 0 ) evenFreq . Add ( freq [ i ] ) ; else oddFreq . Add ( freq [ i ] ) ; } for ( i = 0 ; i < evenFreq . Count ; i ++ ) { sumEven += evenFreq [ i ] ; } if ( oddFreq . Count == 0 ) return 1 ; if ( sumEven == 0 ) { if ( oddFreq . Count == 1 ) return 1 ; return 0 ; } i = 0 ; while ( i < oddFreq . Count ) { if ( ( sumEven / 2 ) % oddFreq . Count == 0 ) return oddFreq . Count ; if ( oddFreq [ i ] == 1 ) { i ++ ; continue ; } sumEven += 2 ; oddFreq . Insert ( i , oddFreq [ i ] - 2 ) ; } return n ; } public static void Main ( String [ ] args ) { String s = " noonpeep " ; Console . WriteLine ( countMinParts ( s ) ) ; } }