Convert string X to an anagram of string Y with minimum replacements | C ++ program to convert string X to string Y which minimum number of changes . ; Function that converts string X into lexicographically smallest anagram of string Y with minimal changes ; Counting frequency of characters in each string . ; We maintain two more counter arrays ctrx [ ] and ctry [ ] Ctrx [ ] maintains the count of extra elements present in string X than string Y Ctry [ ] maintains the count of characters missing from string X which should be present in string Y . ; This means that we cannot edit the current character as it 's frequency  in string X is equal to or less  than the frequency in string Y.  Thus, we go to the next position ; Here , we try to find that character , which has more frequency in string Y and less in string X . We try to find this character in lexicographical order so that we get lexicographically smaller string ; This portion deals with the lexicographical property . Now , we put a character in string X when either this character has smaller value than the character present there right now or if this is the last position for it to exchange , else we fix the character already present here in this position . ; Driver program
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  26 NEW_LINE void printAnagramAndChanges ( string X , string Y ) { int countx [ MAX ] = { 0 } , county [ MAX ] = { 0 } , ctrx [ MAX ] = { 0 } , ctry [ MAX ] = { 0 } ; int change = 0 ; int l = X . length ( ) ; for ( int i = 0 ; i < l ; i ++ ) { countx [ X [ i ] - ' A ' ] ++ ; county [ Y [ i ] - ' A ' ] ++ ; } for ( int i = 0 ; i < MAX ; i ++ ) { if ( countx [ i ] > county [ i ] ) ctrx [ i ] += ( countx [ i ] - county [ i ] ) ; else if ( countx [ i ] < county [ i ] ) ctry [ i ] += ( county [ i ] - countx [ i ] ) ; change += abs ( county [ i ] - countx [ i ] ) ; } for ( int i = 0 ; i < l ; i ++ ) { if ( ctrx [ X [ i ] - ' A ' ] == 0 ) continue ; int j ; for ( j = 0 ; j < MAX ; j ++ ) if ( ( ctry [ j ] ) > 0 ) break ; if ( countx [ X [ i ] - ' A ' ] == ctrx [ X [ i ] - ' A ' ] X [ i ] - ' A ' > j ) { countx [ X [ i ] - ' A ' ] -- ; ctrx [ X [ i ] - ' A ' ] -- ; ctry [ j ] -- ; X [ i ] = ' A ' + j ; } else countx [ X [ i ] - ' A ' ] -- ; } cout << " Anagram ▁ : ▁ " << X << endl ; cout << " Number ▁ of ▁ changes ▁ made ▁ : ▁ " << change / 2 ; } int main ( ) { string x = " CDBABC " , y = " ADCABD " ; printAnagramAndChanges ( x , y ) ; return 0 ; }