4 Ways to check if two Strings are Anagrams in Java | Sorting | Hashing | Using ASCII | Iterating

In this video, I will show you how to check if two Strings are Anagrams of each other. This is one of the most asked Coding Interview Question asked by Big Tech Companies like Google, Amazon, Facebook, Microsoft, Apple and many more.

Before we get into our current topic, here are some of the resources which can help you better understand the current topic.

First of all, what is Anagram?
Two Strings are considered as Anagrams of each other if the characters in the Strings are same but appearing in a different order. For example, RACE and CARE are two different which has the same characters A, C, E and R.
Some other examples of Anagrams are LISTEN and SILENT, FOURTY FIVE and FIFTY FOUR.

Now that we understand our current solution, now lets understand the important questions which needs to be asked before we proceed with a solution. We need to understand following things.

1. What are the sizes of these Strings?
This question is to understand if we can use additional space or we shouldn't. If the size of String is small, then even if we use additional space, it really doesn't matter. But if the size of each String is huge, using Additional space isn't ideal.

2. What is the character set of the Strings? Is it alphabets, alphanumeric, ASCII or any other character?
This question is key for solving in one of the approaches mentioned. If the character set of the String is predefined, then we can take an array of that character set size and count the frequency which can give or solution in one of the Optimal ways.

3. Can we modify the given String?
This question helps us in understanding if we can change the order of characters in the String which is key in one of our techniques. One of our approach is to sort the Strings and compare them to check if they are Anagrams of each other.

4. What happens if one of the Input Strings is null, or both the Strings are null?
This question is essential for helping us understand what to do in case of Edge cases. We pretty much use an assumption that when either of the Strings is null, we don't consider them as Anagrams in all of our approaches.

Now that we understand why these questions are important. Now lets dive into our approaches for the given question.

First Approach: Brute-Force Technique
This approach is pretty straight forward. We take a character from first String and compare it with every character of other string. When a match is found, we replace the character in the second string with some character which isn't part of our character set. And we do that for all the characters in the first string.
Once we complete this process, we check if the second string has all of this replaced characters. If any of the characters is not replaced, then they are not Anagrams.
The time complexity of this approach is O(n^2) and space complexity is O(n).

Second Approach: Sorting and Comparing
In this approach, we convert both the strings into character array and then sort these character arrays, and finally compare these arrays. If they match they are Anagrams otherwise they are not.
The time complexity of this approach is O(nlogn) and space complexity is O(n).

Third Approach: Using and extra array which represents character set (ASCII).
In this approach, we take an additional integer array of size 256 assuming our character set is ASCII, and iterate over these two strings.
For every character from first string we get the ASCII value of that character and increment the value of the ASCII array we have created.
For every character from the second string we get the ASCII value of that character and decrement the value of the ASCII array.
Finally we iterate over the ASCII array and check if any of the values is not equal to zero. If any value is not equal to zero, then they are not Anagrams otherwise they are Anagrams.
The time complexity of this approach is O(n) and space complexity is O(1).

Fourth Approach: Using Hashing
This approach is a little modification of the above mentioned solution. Instead of using a array of defined size, we using Hashing and the rest of the solution would be similar.
For every character from first string, we increment the value of the character in the Hash Map by 1 if it exists, or place a 1 if it doesn't exist in Hash Map.
For every character from second string, we decrement the value of the character in the Hash Map by 1 if it exists, or place a -1 if it doesn't exist in Hash Map.
Once we complete the above steps for all characters in the Strings, we get the values of this Hash Map and check if any of the values is not equal to zero. If any value is not equal to zero, then they are not Anagrams. If they are all zeroes, then they are Anagrams.
The time complexity of this approach is O(n) and the space complexity is O(n).

#Coding #Interviews #Java #Anagram

[samikshavarshney]

3rd and 4th methods are somewhat similar in respect of complexities. Also, can you directly use sort functions in the interviews as used in 2nd method?