Rearrange string to obtain Longest Palindromic Substring | 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
def longestPalinSub ( st ) : NEW_LINE INDENT N = len ( st ) NEW_LINE hash1 = [ 0 ] * 256 NEW_LINE for i in range ( N ) : NEW_LINE INDENT hash1 [ ord ( st [ i ] ) ] += 1 NEW_LINE DEDENT res1 = " " NEW_LINE res2 = " " NEW_LINE for i in range ( 256 ) : NEW_LINE INDENT for j in range ( hash1 [ i ] // 2 ) : NEW_LINE INDENT res1 += chr ( i ) NEW_LINE DEDENT for j in range ( ( hash1 [ i ] + 1 ) // 2 , hash1 [ i ] ) : NEW_LINE INDENT res2 += chr ( i ) NEW_LINE DEDENT DEDENT p = list ( res2 ) NEW_LINE p . reverse ( ) NEW_LINE res2 = ' ' . join ( p ) NEW_LINE res3 = " " NEW_LINE f = False NEW_LINE for i in range ( 256 ) : NEW_LINE INDENT if ( hash1 [ i ] % 2 ) : NEW_LINE INDENT if ( not f ) : NEW_LINE INDENT res1 += chr ( i ) NEW_LINE f = True NEW_LINE DEDENT else : NEW_LINE INDENT res3 += chr ( i ) NEW_LINE DEDENT DEDENT DEDENT return ( res1 + res2 + res3 ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT st = " geeksforgeeks " NEW_LINE print ( longestPalinSub ( st ) ) NEW_LINE DEDENT