Make anagrams from two Strings

Problem Statement

Given two strings, find the total number of characters we need to delete from these strings to make them anagrams of each other.

Understanding Anagrams

Anagrams are defined with respect to a given string of characters (not necessarily characters in the English Alphabet) but a wider set of characters may be.

Given two strings A and B, if the number of time each character occurs in both the string is exactly same, we say A and B are anagrams. However, the order in which the character appears may be different and doesn’t matter.

For example

A = axbbxxcecdeedda
B = abacbddcedxexex

are anagrams because the character count for each of these characters is same as below for both the string:
A = (a = 2, b = 2, c = 2, d = 3, e = 3, x = 3)
B = (a = 2, b = 2, c = 2, d = 3, e = 3, x = 3)

Approaching the problem – Make anagrams from two Strings

There are many ways to solve problems related to anagrams. Here we will discuss two such ways.

Approach 1 – The Sorting Way

Sort the characters in both the string, which can be done by any of the sorting algorithms in O(NlogN) time for most of the algorithms.

We can also employ Count Sort which can get the characters sorted in O(N) time in the best case, using some auxiliary space. More about count sort later.

After sorting the above strings we get the following strings:
A’ = aabbccdddeeexxx
B’ = aabbccdddeeexxx

After this we can follow one of the below two approaches:

  • Now if both A’ and B’ are both equal then A and B are anagrams.
  • The above approach takes space equal to the length of the strings and it is not advisable. So we could have written the string A’ as a2b2c2d3e3x3 and the string B’ as a2b2c2d3e3x3. Hence the space required here is lesser than the first one. If the new A’ and B’ are equal then A and B are anagrams. This way is called signing the string, you can definitely use any other signing methods if it is saving space, also the string comparison will take less time.
Approach 2 – The counting way

This way is mainly an extension of count sort. The idea is to have an auxiliary integer array Counter of length 26 (in case we are dealing with characters from a-z). Such that the value at index 0 represent the number of times the character a appears in the string and so on for b , c , d , e , f etc.

Then traverse through the string A one character at a time and increment the value of the integer stored in the Counter array at the corresponding index.

The array after processing A would be as follows. No matter how big the string is the array will always be of size 26, therefore the space needed is constant O(1).
Make anagrams from two Strings
Now traverse through the string B one character at a time and decrease the value of the integer stored in the Counter array at the corresponding index.

The array after processing B would be as follows:
Make anagrams from two Strings

You may notice that it decremented the values by the count of each character in string B. Each cell in the array now contains a zero, which precisely means that the two strings are anagrams. Because for each character in A there exists a corresponding character in B and it cancels it out.

Note: In case after processing B if the cells were not all zeroes then the number of extra characters which prevent them from being anagrams would be the sum of all the values in all the cells.

For e.g.: Consider the below two strings for the anagram check.
M = abcdefaaxxuvwss
N = defaxuvwsabc

Here is the array after processing M.
Make anagrams from two Strings

And here is it after processing N.
angram

The sum of all the elements in array is 3, it means that there are three extra characters (a, x, s) which prevents the two strings from being anagrams of each other, so we need to delete these three characters.

Source Code – Make anagrams from two Strings

.

Don’t forget to subscribe to TechieMe to get updates on latest posts.