Lexicographically first palindromic string | C ++ 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 program
#include <bits/stdc++.h> NEW_LINE using namespace std ; const char MAX_CHAR = 26 ; void countFreq ( string str , int freq [ ] , int len ) { for ( int i = 0 ; i < len ; i ++ ) freq [ str . at ( i ) - ' a ' ] ++ ; } bool canMakePalindrome ( int freq [ ] , int len ) { int count_odd = 0 ; for ( int 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 ; } string findOddAndRemoveItsFreq ( int freq [ ] ) { string odd_str = " " ; for ( int i = 0 ; i < MAX_CHAR ; i ++ ) { if ( freq [ i ] % 2 != 0 ) { freq [ i ] -- ; odd_str = odd_str + ( char ) ( i + ' a ' ) ; return odd_str ; } } return odd_str ; } string findPalindromicString ( string str ) { int len = str . length ( ) ; int freq [ MAX_CHAR ] = { 0 } ; countFreq ( str , freq , len ) ; if ( ! canMakePalindrome ( freq , len ) ) return " No ▁ Palindromic ▁ String " ; string odd_str = findOddAndRemoveItsFreq ( freq ) ; string front_str = " " , rear_str = " ▁ " ; for ( int i = 0 ; i < MAX_CHAR ; i ++ ) { string temp = " " ; if ( freq [ i ] != 0 ) { char ch = ( char ) ( i + ' a ' ) ; for ( int j = 1 ; j <= freq [ i ] / 2 ; j ++ ) temp = temp + ch ; front_str = front_str + temp ; rear_str = temp + rear_str ; } } return ( front_str + odd_str + rear_str ) ; } int main ( ) { string str = " malayalam " ; cout << findPalindromicString ( str ) ; return 0 ; }