Rearrange string to obtain Longest Palindromic Substring | Java program to implement the above approach ; Function to rearrange the string to get the longest palindromic substring ; Stores the length of str ; Store the count of occurrence of each character ; Traverse the string , str ; Count occurrence of each character ; Store the left half of the longest palindromic substring ; Store the right half of the longest palindromic substring ; Traverse the array , hash [ ] ; Append half of the characters to res1 ; Append half of the characters to res2 ; reverse string res2 to make res1 + res2 palindrome ; Store the remaining characters ; Check If any odd character appended to the middle of the resultant string or not ; Append all the character which occurs odd number of times ; If count of occurrence of characters is odd ; Driver code
import java . util . * ; class GFG { static String longestPalinSub ( String str ) { int N = str . length ( ) ; int [ ] hash = new int [ 256 ] ; for ( int i = 0 ; i < N ; i ++ ) { hash [ str . charAt ( i ) ] ++ ; } StringBuilder res1 = new StringBuilder ( ) ; StringBuilder res2 = new StringBuilder ( ) ; for ( int i = 0 ; i < 256 ; i ++ ) { for ( int j = 0 ; j < hash [ i ] / 2 ; j ++ ) { res1 . append ( ( char ) i ) ; } for ( int j = ( hash [ i ] + 1 ) / 2 ; j < hash [ i ] ; j ++ ) { res2 . append ( ( char ) i ) ; } } StringBuilder tmp = res2 . reverse ( ) ; StringBuilder res3 = new StringBuilder ( ) ; boolean f = false ; for ( int i = 0 ; i < 256 ; i ++ ) { if ( hash [ i ] % 2 == 1 ) { if ( ! f ) { res1 . append ( ( char ) i ) ; f = true ; } else { res3 . append ( ( char ) i ) ; } } } return ( res1 . toString ( ) + tmp . toString ( ) + res3 . toString ( ) ) ; } public static void main ( String [ ] args ) { String str = " geeksforgeeks " ; System . out . println ( longestPalinSub ( str ) ) ; } }