Solution: Valid Anagram
Let's solve the Valid Anagram problem using the Knowing What to Track pattern.
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:
-
str1.length
,str2.length
-
str1
andstr2
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 because of the sorting of the strings, where is the length of the strings. The space complexity of this approach is 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:
- If the lengths of
str1
andstr2
are not equal, thenstr1
andstr2
cannot be anagrams of each other, so return FALSE. - Otherwise, create a lookup hash map
table
, and store the characters as keys and the count of the respective character as its corresponding value. - For storing the count of characters in
str1
, we iterate over the characters instr1
and update the count for each character intable
by incrementing it. - After storing the count of characters in
str1
, we iterate over the characters instr2
and update the count for each character intable
by decrementing it. - Iterate over
table
, and check if the count of any character is not . If so, we know thatstr2
cannot be an anagram ofstr1
because the occurrences of each character in both the strings are not the same, so return FALSE. - If the counts in
table
for all the characters are , it means occurrences of each character in both the strings are the same, andstr2
is an anagram ofstr1
, so return TRUE.
Let’s look at the following illustration to get a better understanding of the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.