Rearrange characters to form palindrome if possible | Python3 program to rearrange a string to make palindrome . ; Store counts of characters ; Find the number of odd elements . Takes O ( n ) ; odd_cnt = 1 only if the length of str is odd ; Generate first halh of palindrome ; Build a string of floor ( count / 2 ) occurrences of current character ; Attach the built string to end of and begin of second half ; Insert odd character if there is any ; Driver code
from collections import defaultdict NEW_LINE def getPalindrome ( st ) : NEW_LINE INDENT hmap = defaultdict ( int ) NEW_LINE for i in range ( len ( st ) ) : NEW_LINE INDENT hmap [ st [ i ] ] += 1 NEW_LINE DEDENT oddCount = 0 NEW_LINE for x in hmap : NEW_LINE INDENT if ( hmap [ x ] % 2 != 0 ) : NEW_LINE INDENT oddCount += 1 NEW_LINE oddChar = x NEW_LINE DEDENT DEDENT if ( oddCount > 1 or oddCount == 1 and len ( st ) % 2 == 0 ) : NEW_LINE INDENT return " NO ▁ PALINDROME " NEW_LINE DEDENT firstHalf = " " NEW_LINE secondHalf = " " NEW_LINE for x in sorted ( hmap . keys ( ) ) : NEW_LINE INDENT s = ( hmap [ x ] // 2 ) * x NEW_LINE firstHalf = firstHalf + s NEW_LINE secondHalf = s + secondHalf NEW_LINE DEDENT if ( oddCount == 1 ) : NEW_LINE INDENT return ( firstHalf + oddChar + secondHalf ) NEW_LINE DEDENT else : NEW_LINE INDENT return ( firstHalf + secondHalf ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " mdaam " NEW_LINE print ( getPalindrome ( s ) ) NEW_LINE DEDENT