Convert string X to an anagram of string Y with minimum replacements | Python3 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 Code
MAX = 26 NEW_LINE def printAnagramAndChanges ( x , y ) : NEW_LINE INDENT x = list ( x ) NEW_LINE y = list ( y ) NEW_LINE countx , county = [ 0 ] * MAX , [ 0 ] * MAX NEW_LINE ctrx , ctry = [ 0 ] * MAX , [ 0 ] * MAX NEW_LINE change = 0 NEW_LINE l = len ( x ) NEW_LINE for i in range ( l ) : NEW_LINE INDENT countx [ ord ( x [ i ] ) - ord ( ' A ' ) ] += 1 NEW_LINE county [ ord ( y [ i ] ) - ord ( ' A ' ) ] += 1 NEW_LINE DEDENT for i in range ( MAX ) : NEW_LINE INDENT if countx [ i ] > county [ i ] : NEW_LINE INDENT ctrx [ i ] += ( countx [ i ] - county [ i ] ) NEW_LINE DEDENT elif countx [ i ] < county [ i ] : NEW_LINE INDENT ctry [ i ] += ( county [ i ] - countx [ i ] ) NEW_LINE DEDENT change += abs ( county [ i ] - countx [ i ] ) NEW_LINE DEDENT for i in range ( l ) : NEW_LINE INDENT if ctrx [ ord ( x [ i ] ) - ord ( ' A ' ) ] == 0 : NEW_LINE INDENT continue NEW_LINE DEDENT j = 0 NEW_LINE for j in range ( MAX ) : NEW_LINE INDENT if ctry [ j ] > 0 : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT if countx [ ord ( x [ i ] ) - ord ( ' A ' ) ] == ctrx [ ord ( x [ i ] ) - ord ( ' A ' ) ] or ord ( x [ i ] ) - ord ( ' A ' ) > j : NEW_LINE INDENT countx [ ord ( x [ i ] ) - ord ( ' A ' ) ] -= 1 NEW_LINE ctrx [ ord ( x [ i ] ) - ord ( ' A ' ) ] -= 1 NEW_LINE ctry [ j ] -= 1 NEW_LINE x [ i ] = chr ( ord ( ' A ' ) + j ) NEW_LINE DEDENT else : NEW_LINE INDENT countx [ ord ( x [ i ] ) - ord ( ' A ' ) ] -= 1 NEW_LINE DEDENT DEDENT print ( " Anagram ▁ : " , ' ' . join ( x ) ) NEW_LINE print ( " Number ▁ of ▁ changes ▁ made ▁ : " , change // 2 ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT x = " CDBABC " NEW_LINE y = " ADCABD " NEW_LINE printAnagramAndChanges ( x , y ) NEW_LINE DEDENT