Rearrange string to obtain Longest Palindromic Substring | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; string longestPalinSub ( string str ) { int N = str . length ( ) ; int hash [ 256 ] = { 0 } ; for ( int i = 0 ; i < N ; i ++ ) { hash [ str [ i ] ] ++ ; } string res1 = " " ; string res2 = " " ; for ( int i = 0 ; i < 256 ; i ++ ) { for ( int j = 0 ; j < hash [ i ] / 2 ; j ++ ) { res1 . push_back ( i ) ; } for ( int j = ( hash [ i ] + 1 ) / 2 ; j < hash [ i ] ; j ++ ) { res2 . push_back ( i ) ; } } reverse ( res2 . begin ( ) , res2 . end ( ) ) ; string res3 ; bool f = false ; for ( int i = 0 ; i < 256 ; i ++ ) { if ( hash [ i ] % 2 ) { if ( ! f ) { res1 . push_back ( i ) ; f = true ; } else { res3 . push_back ( i ) ; } } } return ( res1 + res2 + res3 ) ; } int main ( ) { string str = " geeksforgeeks " ; cout << longestPalinSub ( str ) ; }