Make a lexicographically smallest palindrome with minimal changes | CPP code for changing a string into lexicographically smallest pallindromic string ; Function to create a palindrome ; Count the occurrences of every character in the string ; Create a string of characters with odd occurrences ; Change the created string upto middle element and update count to make sure that only one odd character exists . ; decrease the count of character updated ; Create three strings to make first half second half and middle one . ; characters with even occurrences ; fill the first half . ; character with odd occurrence ; fill the first half with half of occurrence except one ; For middle element ; create the second half by reversing the first half . ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int Palindrome ( string s , int n ) { unordered_map < char , int > cnt ; string R = " " ; for ( int i = 0 ; i < n ; i ++ ) { char a = s [ i ] ; cnt [ a ] ++ ; } for ( char i = ' a ' ; i <= ' z ' ; i ++ ) { if ( cnt [ i ] % 2 != 0 ) R += i ; } int l = R . length ( ) ; int j = 0 ; for ( int i = l - 1 ; i >= l / 2 ; i -- ) { cnt [ R [ i ] ] -- ; R [ i ] = R [ j ] ; cnt [ R [ j ] ] ++ ; j ++ ; } string first , middle , second ; for ( char i = ' a ' ; i <= ' z ' ; i ++ ) { if ( cnt [ i ] != 0 ) { if ( cnt [ i ] % 2 == 0 ) { int j = 0 ; while ( j < cnt [ i ] / 2 ) { first += i ; j ++ ; } } else { int j = 0 ; while ( j < ( cnt [ i ] - 1 ) / 2 ) { first += i ; j ++ ; } middle += i ; } } } second = first ; reverse ( second . begin ( ) , second . end ( ) ) ; string resultant = first + middle + second ; cout << resultant << endl ; } int main ( ) { string S = " geeksforgeeks " ; int n = S . length ( ) ; Palindrome ( S , n ) ; return 0 ; }