242. Valid Anagram - Explanation

Problem Link

Description

Given two strings s and t, return true if the two strings are anagrams of each other, otherwise return false.

An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.

Example 1:

Input: s = "racecar", t = "carrace"

Output: true

Example 2:

Input: s = "jar", t = "jam"

Output: false

Constraints:

• s and t consist of lowercase English letters.

Recommended Time & Space Complexity

You should aim for a solution with O(n + m) time and O(1) space, where n is the length of the string s and m is the length of the string t.

Hint 1

A brute force solution would be to sort the given strings and check for their equality. This would be an O(nlogn + mlogm) solution. Though this solution is acceptable, can you think of a better way without sorting the given strings?

Hint 2

By the definition of the anagram, we can rearrange the characters. Does the order of characters matter in both the strings? Then what matters?

Hint 3

We can just consider maintaining the frequency of each character. We can do this by having two separate hash tables for the two strings. Then, we can check whether the frequency of each character in string s is equal to that in string t and vice versa.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Sorting

Intuition

If two strings are anagrams, they must contain exactly the same characters with the same frequencies.
By sorting both strings, all characters will be arranged in a consistent order.
If the two sorted strings are identical, then every character and its count match, which means the strings are anagrams.

Algorithm

1. If the lengths of the two strings differ, return False immediately because they cannot be anagrams.
2. Sort both strings.
3. Compare the sorted versions of the strings:
   • If they are equal, return True.
   • Otherwise, return False.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        return sorted(s) == sorted(t)

Time & Space Complexity

• Time complexity: $O(n \log n + m \log m)$
• Space complexity: $O(1)$ or $O(n + m)$ depending on the sorting algorithm.

Where $n$ is the length of string $s$ and $m$ is the length of string $t$.

---

2. Hash Map

Intuition

If two strings are anagrams, they must use the same characters with the same frequencies.
Instead of sorting, we can count how many times each character appears in both strings.
By using two hash maps (or dictionaries), we track the frequency of every character in each string.
If both frequency maps match exactly, then the strings contain the same characters with same frequencies, meaning they are anagrams.

Algorithm

1. If the two strings have different lengths, return False immediately.
2. Create two hash maps to store character frequencies for each string.
3. Iterate through both strings at the same time:
   • Increase the character count for s[i] in the first map.
   • Increase the character count for t[i] in the second map.
4. After building both maps, compare them:
   • If the maps are equal, return True.
   • Otherwise, return False.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        countS, countT = {}, {}

        for i in range(len(s)):
            countS[s[i]] = 1 + countS.get(s[i], 0)
            countT[t[i]] = 1 + countT.get(t[i], 0)
        return countS == countT

Time & Space Complexity

• Time complexity: $O(n + m)$
• Space complexity: $O(1)$ since we have at most $26$ different characters.

Where $n$ is the length of string $s$ and $m$ is the length of string $t$.

---

3. Hash Table (Using Array)

Intuition

Since the problem guarantees lowercase English letters, we can use a fixed-size array of length 26 to count character frequencies instead of a hash map.
As we iterate through both strings simultaneously, we increment the count for each character in s and decrement the count for each character in t.
If the strings are anagrams, every increment will be matched by a corresponding decrement, and all values in the array will end at zero.
This approach is efficient because it avoids hashing and uses constant space.

Algorithm

1. If the lengths of the strings differ, return False immediately.
2. Create a frequency array count of size 26 initialized to zero.
3. Iterate through both strings:
   • Increment the count at the index corresponding to s[i].
   • Decrement the count at the index corresponding to t[i].
4. After processing both strings, scan through the count array:
   • If any value is not zero, return False because the frequencies differ.
5. If all values are zero, return True since the strings are anagrams.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        count = [0] * 26
        for i in range(len(s)):
            count[ord(s[i]) - ord('a')] += 1
            count[ord(t[i]) - ord('a')] -= 1

        for val in count:
            if val != 0:
                return False
        return True

Time & Space Complexity

• Time complexity: $O(n + m)$
• Space complexity: $O(1)$ since we have at most $26$ different characters.

Where $n$ is the length of string $s$ and $m$ is the length of string $t$.