*1.3K*

Question: Given a two strings, find the minimum number of characters that must be deleted to make them anagrams.

Input: str1 = “a b c”, str2 = “a m n o p”Output: 6

Let us try to understand this problem statement and its test case first.

We have two strings of english alphabet which may or may not have the same length. Anagrams are two words with same characters and frequencies. It is not necessary that the order of the characters is same. We have to determine, how many total number of characters must be deleted from these `2`

strings, such that they become anagrams.

Let us look at test cases:

If you look at the word `rat`

and the word `tars`

, notice that if we delete the last character `s`

from `str2`

, it would become `tar`

. This word has the exact same characters as the word `rat`

. Hence, we can say that by deleting a total of `1`

character(s), the words can be made anagrams.

Similarly, in the second test case, if we delete `de`

from str1 and `ab`

from str2, we delete a total of `4`

characters. The image below gives a better idea.

#### Method 1:

You need to take advantage of the fact, that two words would be anagrams iff they have the exact same characters and frequencies. A brute force method to solve this problem is quite straight forward.

- Start with the first character in
`str1`

. Iterate through the second string and search if the character is present. - If we find this character, mark it as visited. Otherwise, this character becomes a candidate for deletion. Increase the delete count of
`str1`

by`1`

. - Do this process for each character of
`str1`

. - Similarly, now start with each character of
`str2`

. Try to find the character in`str1`

. - If found, mark it as visited, else increase the delete count of
`str2`

by`1`

. - Now count the number of characters we need to delete from both the strings.

#### Method 2 (Efficient Solution):

The above method works perfectly, but you end up wasting a lot of time iterating over both the strings multiple number of times. We need an optimized approach.

One way to approach the problem is by creating a bucket of each character. Counting sort also works on a similar approach. You initialize an array of `26`

integers. Each index holds the frequency of a single character.

arr[0] holds frequency ofaarr[1] holds frequency ofb. . arr[25] holds frequency ofz

We can now take advantage of this.

- Iterate through the first string and increment the indexes corresponding to each character.
- Next, go over the second string and decrement the indexes corresponding to each character.

The characters that occurred same number of times will have their frequency changed to `0`

. The extra characters would have some frequency remaining. The sum of all these frequencies will determine how many characters need to be deleted in order to make these `2`

strings anagrams.

#### Code:

```
int makingAnagrams(String s1, String s2) {
int[] c = new int[26];
s1 = s1.toLowerCase();
s2 = s2.toLowerCase();
for (int i = 0; i < s1.length(); i++) {
c[s1.charAt(i) - 'a']++;
}
for (int i = 0; i < s2.length(); i++) {
c[s2.charAt(i) - 'a']--;
}
int total = 0;
for (int i : c) {
total += Math.abs(i);
}
return total;
}
```

Code language: Java (java)

*Time Complexity:* O(n)*Space Complexity:* O(1)