Form minimum number of Palindromic Strings from a given string | C ++ Program to implement the above approach ; Function to return minimum palindromic strings formed ; Store the length of string ; Iterate over the string and store the frequency of all charactrs A vector to store the frequency ; Store the odd frequency characters ; Iterate through all possible characters and check the parity of frequency ; store answer in a vector ; if there are no odd Frequency characters then print the string with even characters ; store the left part of the palindromic string ; reverse the right part of the string ; store the string in ans vector ; take any character from off frequency element ; repeat the above step to form left and right strings ; reverse the right part of the string ; store the string in ans vector ; store all other odd frequency strings ; Print the answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minimumPalindromicStrings ( string S ) { int N = S . length ( ) ; vector < int > freq ( 26 ) ; for ( int i = 0 ; i < N ; i ++ ) { freq [ S [ i ] - ' a ' ] ++ ; } vector < int > oddFreqCharacters ; for ( int i = 0 ; i < 26 ; i ++ ) { if ( freq [ i ] & 1 ) { oddFreqCharacters . push_back ( i ) ; freq [ i ] -- ; } freq [ i ] /= 2 ; } vector < string > ans ; if ( oddFreqCharacters . empty ( ) ) { 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 ( right . begin ( ) , right . end ( ) ) ; ans . push_back ( left + right ) ; } else { string middle = " " ; int c = oddFreqCharacters . back ( ) ; oddFreqCharacters . pop_back ( ) ; middle += char ( c + ' a ' ) ; 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 ( right . begin ( ) , right . end ( ) ) ; ans . push_back ( left + middle + right ) ; while ( ! oddFreqCharacters . empty ( ) ) { int c = oddFreqCharacters . back ( ) ; oddFreqCharacters . pop_back ( ) ; string middle = " " ; middle += char ( c + ' a ' ) ; ans . push_back ( middle ) ; } } cout << " [ " ; for ( int i = 0 ; i < ans . size ( ) ; i ++ ) { cout << ans [ i ] ; if ( i != ans . size ( ) - 1 ) { cout << " , ▁ " ; } } cout << " ] " ; return 0 ; } int main ( ) { string S = " geeksforgeeks " ; minimumPalindromicStrings ( S ) ; }