Make a lexicographically smallest palindrome with minimal changes | Function to create a palindrome ; Count the occurrences of every character in the string ; Create a string of characters with odd occurrences ; Change the created string upto middle element and update count to make sure that only one odd character exists . ; decrease the count of character updated ; Create three strings to make first half second half and middle one . ; characters with even occurrences ; fill the first half . ; character with odd occurrence ; fill the first half with half of occurrence except one ; For middle element ; create the second half by reversing the first half . ; Driver Code
def palindrome ( s : str , n : int ) -> int : NEW_LINE INDENT cnt = dict ( ) NEW_LINE R = [ ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT a = s [ i ] NEW_LINE if a in cnt : NEW_LINE INDENT cnt [ a ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT cnt [ a ] = 1 NEW_LINE DEDENT DEDENT i = ' a ' NEW_LINE while i <= ' z ' : NEW_LINE INDENT if i in cnt and cnt [ i ] % 2 != 0 : NEW_LINE INDENT R += i NEW_LINE DEDENT i = chr ( ord ( i ) + 1 ) NEW_LINE DEDENT l = len ( R ) NEW_LINE j = 0 NEW_LINE for i in range ( l - 1 , ( l // 2 ) - 1 , - 1 ) : NEW_LINE INDENT if R [ i ] in cnt : NEW_LINE INDENT cnt [ R [ i ] ] -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT cnt [ R [ i ] ] = - 1 NEW_LINE DEDENT R [ i ] = R [ j ] NEW_LINE if R [ j ] in cnt : NEW_LINE INDENT cnt [ R [ j ] ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT cnt [ R [ j ] ] = 1 NEW_LINE DEDENT j += 1 NEW_LINE DEDENT first , middle , second = " " , " " , " " NEW_LINE i = ' a ' NEW_LINE while i <= ' z ' : NEW_LINE INDENT if i in cnt : NEW_LINE INDENT if cnt [ i ] % 2 == 0 : NEW_LINE INDENT j = 0 NEW_LINE while j < cnt [ i ] // 2 : NEW_LINE INDENT first += i NEW_LINE j += 1 NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT j = 0 NEW_LINE while j < ( cnt [ i ] - 1 ) // 2 : NEW_LINE INDENT first += i NEW_LINE j += 1 NEW_LINE DEDENT middle += i NEW_LINE DEDENT DEDENT i = chr ( ord ( i ) + 1 ) NEW_LINE DEDENT second = first NEW_LINE second = ' ' . join ( reversed ( second ) ) NEW_LINE resultant = first + middle + second NEW_LINE print ( resultant ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT S = " geeksforgeeks " NEW_LINE n = len ( S ) NEW_LINE palindrome ( S , n ) NEW_LINE DEDENT