Rearrange characters to form palindrome if possible | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; string getPalindrome ( string str ) { unordered_map < char , int > hmap ; for ( int i = 0 ; i < str . length ( ) ; i ++ ) hmap [ str [ i ] ] ++ ; int oddCount = 0 ; char oddChar ; for ( auto x : hmap ) { if ( x . second % 2 != 0 ) { oddCount ++ ; oddChar = x . first ; } } if ( oddCount > 1 || oddCount == 1 && str . length ( ) % 2 == 0 ) return " NO ▁ PALINDROME " ; string firstHalf = " " , secondHalf = " " ; for ( auto x : hmap ) { string s ( x . second / 2 , x . first ) ; firstHalf = firstHalf + s ; secondHalf = s + secondHalf ; } return ( oddCount == 1 ) ? ( firstHalf + oddChar + secondHalf ) : ( firstHalf + secondHalf ) ; } int main ( ) { string s = " mdaam " ; cout << getPalindrome ( s ) ; return 0 ; }