Lexicographically first palindromic string | PHP 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
< ? php $ MAX_CHAR = 26 ; function countFreq ( $ str , & $ freq , $ len ) { for ( $ i = 0 ; $ i < $ len ; $ i ++ ) $ freq [ ord ( $ str [ $ i ] ) - ord ( ' a ' ) ] ++ ; } function canMakePalindrome ( $ freq , $ len ) { global $ MAX_CHAR ; $ count_odd = 0 ; for ( $ i = 0 ; $ i < $ MAX_CHAR ; $ i ++ ) if ( $ freq [ $ i ] % 2 != 0 ) $ count_odd ++ ; if ( $ len % 2 == 0 ) { if ( $ count_odd > 0 ) return false ; else return true ; } if ( $ count_odd != 1 ) return false ; return true ; } function findOddAndRemoveItsFreq ( $ freq ) { global $ MAX_CHAR ; $ odd_str = " " ; for ( $ i = 0 ; $ i < $ MAX_CHAR ; $ i ++ ) { if ( $ freq [ $ i ] % 2 != 0 ) { $ freq [ $ i ] -- ; $ odd_str . = chr ( $ i + ord ( ' a ' ) ) ; return $ odd_str ; } } return $ odd_str ; } function findPalindromicString ( $ str ) { global $ MAX_CHAR ; $ len = strlen ( $ str ) ; $ freq = array_fill ( 0 , $ MAX_CHAR , 0 ) ; countFreq ( $ str , $ freq , $ len ) ; if ( ! canMakePalindrome ( $ freq , $ len ) ) return " No ▁ Palindromic ▁ String " ; $ odd_str = findOddAndRemoveItsFreq ( $ freq ) ; $ front_str = " " ; $ rear_str = " ▁ " ; for ( $ i = 0 ; $ i < $ MAX_CHAR ; $ i ++ ) { $ temp = " " ; if ( $ freq [ $ i ] != 0 ) { $ ch = chr ( $ i + ord ( ' a ' ) ) ; for ( $ j = 1 ; $ j <= ( int ) ( $ freq [ $ i ] / 2 ) ; $ j ++ ) $ temp . = $ ch ; $ front_str . = $ temp ; $ rear_str = $ temp . $ rear_str ; } } return ( $ front_str . $ odd_str . $ rear_str ) ; } $ str = " malayalam " ; echo findPalindromicString ( $ str ) ; ? >