Lexicographically first palindromic string | Python3 program to find first palindromic permutation of given string ; Function to count frequency of each char in the string . freq [ 0 ] for ' a ' , ... . , freq [ 25 ] for 'z ; Cases to check whether a palindr0mic string can be formed or not ; count_odd to count no of chars with odd frequency ; For even length string no odd freq character ; For odd length string one odd freq character ; Function to find odd freq char and reducing its freq by 1 returns " " if odd freq char is not present ; To find lexicographically first palindromic string . ; Assigning odd freq character if present else empty string . ; Traverse characters in increasing order ; Divide all occurrences into two halves . Note that odd character is removed by findOddAndRemoveItsFreq ( ) ; creating front string ; creating rear string ; Final palindromic string which is lexicographically first ; Driver code
MAX_CHAR = 26 ; NEW_LINE ' NEW_LINE def countFreq ( str1 , freq , len1 ) : NEW_LINE INDENT for i in range ( len1 ) : NEW_LINE INDENT freq [ ord ( str1 [ i ] ) - ord ( ' a ' ) ] += 1 ; NEW_LINE DEDENT DEDENT def canMakePalindrome ( freq , len1 ) : NEW_LINE INDENT count_odd = 0 ; NEW_LINE for i in range ( MAX_CHAR ) : NEW_LINE INDENT if ( freq [ i ] % 2 != 0 ) : NEW_LINE INDENT count_odd += 1 ; NEW_LINE DEDENT DEDENT if ( len1 % 2 == 0 ) : NEW_LINE INDENT if ( count_odd > 0 ) : NEW_LINE INDENT return False ; NEW_LINE DEDENT else : NEW_LINE INDENT return True ; NEW_LINE DEDENT DEDENT if ( count_odd != 1 ) : NEW_LINE INDENT return False ; NEW_LINE DEDENT return True ; NEW_LINE DEDENT def findOddAndRemoveItsFreq ( freq ) : NEW_LINE INDENT odd_str = " " ; NEW_LINE for i in range ( MAX_CHAR ) : NEW_LINE INDENT if ( freq [ i ] % 2 != 0 ) : NEW_LINE INDENT freq [ i ] -= 1 ; NEW_LINE odd_str += chr ( i + ord ( ' a ' ) ) ; NEW_LINE return odd_str ; NEW_LINE DEDENT DEDENT return odd_str ; NEW_LINE DEDENT def findPalindromicString ( str1 ) : NEW_LINE INDENT len1 = len ( str1 ) ; NEW_LINE freq = [ 0 ] * MAX_CHAR ; NEW_LINE countFreq ( str1 , freq , len1 ) ; NEW_LINE if ( canMakePalindrome ( freq , len1 ) == False ) : NEW_LINE INDENT return " No ▁ Palindromic ▁ String " ; NEW_LINE DEDENT odd_str = findOddAndRemoveItsFreq ( freq ) ; NEW_LINE front_str = " " ; NEW_LINE rear_str = " ▁ " ; NEW_LINE for i in range ( MAX_CHAR ) : NEW_LINE INDENT temp = " " ; NEW_LINE if ( freq [ i ] != 0 ) : NEW_LINE INDENT ch = chr ( i + ord ( ' a ' ) ) ; NEW_LINE for j in range ( 1 , int ( freq [ i ] / 2 ) + 1 ) : NEW_LINE INDENT temp += ch ; NEW_LINE DEDENT front_str += temp ; NEW_LINE rear_str = temp + rear_str ; NEW_LINE DEDENT DEDENT return ( front_str + odd_str + rear_str ) ; NEW_LINE DEDENT str1 = " malayalam " ; NEW_LINE print ( findPalindromicString ( str1 ) ) ; NEW_LINE