Given two strings, how do we find the number of characters to be deleted from both the strings in order to make them anagrams.
Two words are said to be anagrams if one word can be formed by re-arranging the letters of another word. For example the words “TAN” and “ANT” are anagrams.
Given two words “clean” and “lion”, we need to delete 5 characters from both the strings, {c,e,a} from the first and {i,o} from the second.
Let us discuss the approach to solve this problem.
If two words are anagrams, they both have same set of characters along with their counts. So to make two random words as anagrams, we have to delete all the characters that are present in one word but not in the other word.
To do this
- We first create the frequency table of each character present in the first word.
- Next we iterate through each character in the second word, and try to find it in the frequency table.
- If there is a non zero count for that character, we decrement it.
- Otherwise we need to delete the character.
- After processing all the characters in the second word, we need to delete if there are any extra characters present in the table.
Here is the Python program which implements the same.