Solution: Valid Anagram

Statement

Given two strings, str1 and str2, check whether str2 is an anagram of str1.

An anagram is a word or phrase created by rearranging the letters of another word or phrase while utilizing each of the original letters exactly once.

Constraints:

• $1 \leq$ str1.length, str2.length $\leq 10^3$

• str1 and str2 consist of only lowercase English letters.

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

A naive approach to solve this problem is to check whether the strings str1 and str2 are of equal length. If the length of both the strings is different, then str2 is not an anagram of str1. If str1 and str2 are of equal length, sort the characters in both strings. After sorting, iterate over the characters in both strings and check whether they are identical at each position. If all the characters are identical, return TRUE. Otherwise, return FALSE.

The time complexity of this approach is $O(nlogn)$ because of the sorting of the strings, where $n$ is the length of the strings. The space complexity of this approach is $O(1)$ because we are not using any additional memory.

Optimized approach using frequency counting

The frequency counting approach would solve this problem in linear time and with constant space complexity. The approach demands that we keep track of the count of characters so we can verify if the characters of the string str1 have appeared the same number of times in the string str2. The algorithm proceeds through the following steps:

1. If the lengths of str1 and str2 are not equal, then str1 and str2 cannot be anagrams of each other, so return FALSE.
2. Otherwise, create a lookup hash map table, and store the characters as keys and the count of the respective character as its corresponding value.
3. For storing the count of characters in str1, we iterate over the characters in str1 and update the count for each character in table by incrementing it.
4. After storing the count of characters in str1, we iterate over the characters in str2 and update the count for each character in table by decrementing it.
5. Iterate over table, and check if the count of any character is not $0$. If so, we know that str2 cannot be an anagram of str1 because the occurrences of each character in both the strings are not the same, so return FALSE.
6. If the counts in table for all the characters are $0$, it means occurrences of each character in both the strings are the same, and str2 is an anagram of str1, so return TRUE.

Let’s look at the following illustration to get a better understanding of the solution: