Problem Description

You are given two strings s and t. Your task is to determine if string t is an anagram of string s.

An anagram means that string t contains exactly the same characters as string s, but possibly in a different order. In other words, you can rearrange the letters of s to form t.

Return true if t is an anagram of s, and false otherwise.

For example:

• If s = "anagram" and t = "nagaram", the function should return true because both strings contain the same characters with the same frequencies (a:3, n:1, g:1, r:1, m:1).
• If s = "rat" and t = "car", the function should return false because they contain different characters.

The key insight is that two strings are anagrams if and only if they contain the exact same characters with the exact same frequencies - just potentially arranged in a different order.

Intuition

To check if two strings are anagrams, we need to verify that they contain the exact same characters with the exact same frequencies. Think of it like having two bags of letters - they're anagrams if both bags contain identical sets of letters.

The most straightforward observation is that anagrams must have the same length. If one string is longer than the other, they can't possibly be anagrams since one would have extra characters.

Once we know the strings have equal length, we need to count and compare character frequencies. We can think of this as creating an inventory of characters in the first string, then checking if the second string matches this inventory exactly.

A clever approach is to use a counter or hash table to track character frequencies from the first string s. Then, as we go through the second string t, we "consume" characters from our counter by decrementing their counts. If at any point we try to use a character that we don't have enough of (count goes below 0), we know t contains characters that aren't available in the right quantities from s, so they can't be anagrams.

This approach is efficient because we only need one pass through each string, and we can exit early if we find a mismatch. If we successfully process all characters in t without any count going negative, the strings must be anagrams.

Solution Approach

The solution uses a counting approach with a hash table to verify if two strings are anagrams.

Step 1: Length Check
First, we compare the lengths of strings s and t. If len(s) != len(t), we immediately return false since strings of different lengths cannot be anagrams.

Step 2: Character Counting
We create a counter (hash table) to store the frequency of each character in string s. The Counter(s) creates a dictionary where keys are characters and values are their frequencies. For example, if s = "aab", the counter would be {'a': 2, 'b': 1}.

Step 3: Character Verification
We iterate through each character c in string t:

• Decrement the count for character c in our counter: cnt[c] -= 1
• Check if the count becomes negative: if cnt[c] < 0
• If any count goes below 0, it means t has more occurrences of that character than s, so they cannot be anagrams - return false

Step 4: Final Result
If we successfully process all characters in t without any count going negative, return true. This means every character in t exists in s with the correct frequency.

The algorithm has a time complexity of O(n) where n is the length of the strings, since we traverse each string once. The space complexity is O(k) where k is the number of unique characters in string s, which in the worst case could be O(26) for lowercase English letters, making it effectively O(1).

This approach is optimal because it only requires one pass through each string and can detect non-anagrams early by returning as soon as a mismatch is found.

Example Walkthrough

Let's walk through the solution with a concrete example where s = "listen" and t = "silent".

Step 1: Length Check

• Length of s = "listen" is 6
• Length of t = "silent" is 6
• Since lengths are equal, we proceed to the next step

Step 2: Build Character Counter from s We create a counter from string s = "listen":

Counter = {
  'l': 1,
  'i': 1,
  's': 1,
  't': 1,
  'e': 1,
  'n': 1
}

Step 3: Process Each Character in t = "silent"

Now we iterate through each character in t and decrement the counter:

• Character 's': Counter['s'] = 1 - 1 = 0 ✓ (not negative, continue)
• Character 'i': Counter['i'] = 1 - 1 = 0 ✓ (not negative, continue)
• Character 'l': Counter['l'] = 1 - 1 = 0 ✓ (not negative, continue)
• Character 'e': Counter['e'] = 1 - 1 = 0 ✓ (not negative, continue)
• Character 'n': Counter['n'] = 1 - 1 = 0 ✓ (not negative, continue)
• Character 't': Counter['t'] = 1 - 1 = 0 ✓ (not negative, continue)

Final counter state:

Counter = {
  'l': 0,
  'i': 0,
  's': 0,
  't': 0,
  'e': 0,
  'n': 0
}

Step 4: Return Result Since we processed all characters in t without any count going negative, we return true. The strings "listen" and "silent" are anagrams!

Counter-Example: Non-Anagram Case

Let's also see what happens with s = "rat" and t = "car":

1. Both strings have length 3, so we continue
2. Build counter from s = "rat": Counter = {'r': 1, 'a': 1, 't': 1}
3. Process t = "car":
   • Character 'c': Counter['c'] = 0 - 1 = -1 ✗ (negative!)

Since the counter for 'c' becomes negative (because 'c' doesn't exist in s), we immediately return false. The strings are not anagrams.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string. The algorithm first checks if the lengths are equal (constant time), then creates a Counter for string s which takes O(n) time, and finally iterates through string t once, performing constant-time operations for each character, which also takes O(n) time. Overall, this gives us O(n) + O(n) = O(n).

The space complexity is O(C), where C is the size of the character set. The Counter object stores at most C unique characters. Since this problem deals with lowercase English letters, C = 26, making the space complexity O(26) = O(1) in terms of constant space.

Common Pitfalls

Pitfall 1: Forgetting the Length Check

One common mistake is jumping straight into character counting without first checking if the strings have equal lengths. This can lead to unnecessary computation and incorrect results.

Incorrect approach:

def isAnagram(self, s: str, t: str) -> bool:
    char_count = Counter(s)
    for char in t:
        char_count[char] -= 1
        if char_count[char] < 0:
            return False
    # Bug: If t is shorter than s, we might return True incorrectly
    return True

Why it fails: If s = "abc" and t = "ab", the function would return True because all characters in t exist in s, but they're not anagrams since s has an extra 'c'.

Solution: Always check lengths first before any other processing.

Pitfall 2: Using Default Dictionary Behavior Incorrectly

When using Counter, accessing a non-existent key returns 0 by default. However, if you use a regular dictionary, accessing a missing key throws a KeyError.

Incorrect approach with regular dict:

def isAnagram(self, s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
  
    char_count = {}
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1
  
    for char in t:
        char_count[char] -= 1  # KeyError if char not in s
        if char_count[char] < 0:
            return False
    return True

Solution: Either use Counter (which handles missing keys gracefully) or check key existence before decrementing:

for char in t:
    if char not in char_count:
        return False
    char_count[char] -= 1
    if char_count[char] < 0:
        return False

Pitfall 3: Inefficient Double-Pass Verification

Some implementations count both strings and then compare the counters, which requires two full passes and additional comparison logic.

Less efficient approach:

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

While this works correctly and is readable, it always processes both strings completely even when an early mismatch could be detected. The provided solution can return early when it finds a character in t that exceeds its frequency in s, making it more efficient for non-anagram cases.