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.

Input and Output

Item	Meaning
Input	Strings s and t
Output	True if they are anagrams, otherwise False
Character set	Lowercase English letters
Requirement	Same character frequencies

Function shape:

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

Examples

Example 1:

s = "anagram"
t = "nagaram"

Character counts:

Character	Count
a	3
n	1
g	1
r	1
m	1

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:

Character	Frequency
a	3
n	1
g	1
r	1
m	1

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:

Character	Count
a	1
b	1
c	1

Process t:

Character	New Count
b	0
c	0
a	0

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

Metric	Value	Why
Time	O(n)	Each character is processed once
Space	O(1)	At most 26 lowercase English letters

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()

Test	Why
"anagram" vs "nagaram"	Standard valid example
"rat" vs "car"	Different characters
Empty strings	Minimum boundary
Single character	Small valid case
"ab" vs "ba"	Different order
"aacc" vs "ccac"	Frequency mismatch
"listen" vs "silent"	Common anagram pair