Form minimum number of Palindromic Strings from a given string | Java 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
import java . util . * ; class GFG { static int minimumPalindromicStrings ( String S ) { int N = S . length ( ) ; int [ ] freq = new int [ 26 ] ; for ( int i = 0 ; i < N ; i ++ ) { freq [ S . charAt ( i ) - ' a ' ] ++ ; } Vector < Integer > oddFreqCharacters = new Vector < Integer > ( ) ; for ( int i = 0 ; i < 26 ; i ++ ) { if ( freq [ i ] % 2 == 1 ) { oddFreqCharacters . add ( i ) ; freq [ i ] -- ; } freq [ i ] /= 2 ; } Vector < String > ans = new Vector < String > ( ) ; if ( oddFreqCharacters . isEmpty ( ) ) { String left = " " ; for ( int i = 0 ; i < 26 ; i ++ ) { for ( int j = 0 ; j < freq [ i ] ; j ++ ) { left += ( char ) ( i + ' a ' ) ; } } String right = left ; right = reverse ( right ) ; ans . add ( left + right ) ; } else { String middle = " " ; int c = oddFreqCharacters . lastElement ( ) ; oddFreqCharacters . remove ( oddFreqCharacters . size ( ) - 1 ) ; 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 ; right = reverse ( right ) ; ans . add ( left + middle + right ) ; while ( ! oddFreqCharacters . isEmpty ( ) ) { c = oddFreqCharacters . lastElement ( ) ; oddFreqCharacters . remove ( oddFreqCharacters . size ( ) - 1 ) ; middle = " " ; middle += ( char ) ( c + ' a ' ) ; ans . add ( middle ) ; } } System . out . print ( " [ " ) ; for ( int i = 0 ; i < ans . size ( ) ; i ++ ) { System . out . print ( ans . get ( i ) ) ; if ( i != ans . size ( ) - 1 ) { System . out . print ( " , ▁ " ) ; } } System . out . print ( " ] " ) ; return 0 ; } static String reverse ( String input ) { char [ ] a = input . toCharArray ( ) ; int l , r = a . length - 1 ; for ( l = 0 ; l < r ; l ++ , r -- ) { char temp = a [ l ] ; a [ l ] = a [ r ] ; a [ r ] = temp ; } return String . valueOf ( a ) ; } public static void main ( String [ ] args ) { String S = " geeksforgeeks " ; minimumPalindromicStrings ( S ) ; } }