LeetCode 242: Valid Anagram

Problem Restatement

We are given two strings:

s and t

We need to determine whether t is an anagram of s.

Two strings are anagrams if:

• They contain exactly the same characters
• Every character appears the same number of times

The order does not matter.

LeetCode examples include:

Input:  s = "anagram", t = "nagaram"
Output: true

and:

Input:  s = "rat", t = "car"
Output: false

The problem constraints use lowercase English letters. The follow-up asks how to handle Unicode characters. (leetcode.com)

Input and Output

Function shape:

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        ...

Examples

Example 1:

s = "anagram"
t = "nagaram"

Character counts:

Both strings contain exactly the same frequencies.

So the answer is:

True

Example 2:

s = "rat"
t = "car"

The character counts differ.

For example:

'r' appears in s
'c' appears in t

So the answer is:

False

First Thought: Sort Both Strings

If two strings are anagrams, then sorting them should produce the same result.

Example:

"anagram" -> "aaagmnr"
"nagaram" -> "aaagmnr"

So we can write:

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

This works and is very concise.

But sorting costs:

O(n log n)

We can do better with counting.

Key Insight

Anagrams are defined by character frequencies.

So instead of sorting, we count how many times each character appears.

If every character frequency matches, the strings are anagrams.

Otherwise, they are not.

Frequency Counting

For:

s = "anagram"

the counts are:

For:

t = "nagaram"

the counts are identical.

So the strings are anagrams.

Algorithm

1. If the lengths differ, return False.
2. Count character frequencies in s.
3. Count character frequencies in t.
4. Compare the two frequency maps.

If they are equal, return True.

Otherwise, return False.

Using One Hash Map

We can optimize slightly.

Instead of building two separate maps:

1. Increment counts using s
2. Decrement counts using t
3. At the end, every count must be zero

Example:

s = "abc"
t = "bca"

Process s:

Process t:

All counts become zero, so the strings are anagrams.

Correctness

If two strings are anagrams, then every character appears the same number of times in both strings.

The algorithm increments counts for characters in s and decrements counts for characters in t.

For any character:

• Matching frequencies produce a final count of zero.
• Different frequencies produce a nonzero final count.

Therefore:

• If all counts are zero, the strings contain exactly the same character frequencies, so they are anagrams.
• If any count is nonzero, some character frequency differs, so they are not anagrams.

The length check is also necessary. Two strings of different lengths cannot have identical character frequencies.

Therefore, the algorithm returns True exactly when the strings are anagrams.

Complexity

If Unicode characters are allowed, the space complexity becomes:

O(k)

where k is the number of distinct characters.

Implementation

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

        count = {}

        for ch in s:
            count[ch] = count.get(ch, 0) + 1

        for ch in t:
            count[ch] = count.get(ch, 0) - 1

        for value in count.values():
            if value != 0:
                return False

        return True

Code Explanation

First check lengths:

if len(s) != len(t):
    return False

Different lengths immediately rule out anagrams.

Create the frequency map:

count = {}

Count characters from s:

for ch in s:
    count[ch] = count.get(ch, 0) + 1

Then subtract frequencies using t:

for ch in t:
    count[ch] = count.get(ch, 0) - 1

Finally, verify every count became zero:

for value in count.values():
    if value != 0:
        return False

If all counts are zero:

return True

Alternative: collections.Counter

Python provides a built-in frequency counter.

from collections import Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)

This is concise and readable.

Internally, it uses the same counting idea.

Unicode Follow-Up

If Unicode characters are allowed, fixed-size arrays for 26 letters no longer work.

Hash maps remain valid because they can store arbitrary characters.

So the counting approach still works naturally for Unicode strings.

Testing

def run_tests():
    s = Solution()

    assert s.isAnagram("anagram", "nagaram") is True
    assert s.isAnagram("rat", "car") is False
    assert s.isAnagram("", "") is True
    assert s.isAnagram("a", "a") is True
    assert s.isAnagram("ab", "ba") is True
    assert s.isAnagram("aacc", "ccac") is False
    assert s.isAnagram("listen", "silent") is True

    print("all tests passed")

run_tests()