LeetCode #242 Easy

Valid Anagram

Return true if t is an anagram of s — the same letters with the same counts, in any order.

stringhash-tablecounting

02

Intuition

Anagrams have identical letter tallies. Add one for each letter of s and subtract one for each letter of t; if everything cancels to zero, they match.

How to spot this pattern

Counting, not sorting. A fixed 26-slot array beats a hash map when the alphabet is known and small, and the single-pass increment/decrement trick means one loop instead of two maps compared at the end. Whenever the domain is bounded, an array indexed by the character is the hash map, without the hashing.

03

Approach

1

Sorting works but does more than needed

Two strings are anagrams iff they have the same letters with the same counts. Sorting both and comparing proves this in O(n log n) — fine, but order is irrelevant to the question, so paying to order the characters is wasted effort. What we actually care about is the tally of each letter.

2

Cancel s against t in one tally

Use a 26-slot count array (lowercase letters). Walk both strings together: add 1 for each letter of s and subtract 1 for each letter of t. If the two are anagrams, every letter contributed and removed the same number of times, so all 26 counts end at exactly 0. Any imbalance leaves a non-zero entry. Counting is inherently order-independent, which is precisely why it fits this problem better than sorting.

3

Reject length mismatch, then verify all zeros

First a cheap guard: different lengths can't be anagrams, so return false immediately. Otherwise run the single combined loop and check that every count is zero. The count array is a fixed 26 entries regardless of input size, giving O(n) time and O(1) space.

04

Solution & live demo

▶1class Solution:
▶2    def isAnagram(self, s, t):
▶3        if len(s) != len(t):
▶4            return False
▶5        counts = [0] * 26
▶6        for a, b in zip(s, t):
▶7            counts[ord(a) - ord('a')] += 1
▶8            counts[ord(b) - ord('a')] -= 1
▶9        return all(c == 0 for c in counts)

05

Common pitfalls

Sorting both strings

✗ Wrong

return sorted(s) == sorted(t)

✓ Right

counts = [0] * 26
for a, b in zip(s, t): ...

Correct and a fine one-liner, but O(n log n) where counting is O(n). The interviewer asking this question is usually looking for the counting insight.

Skipping the length check

✗ Wrong

counts = [0] * 26
for a, b in zip(s, t): ...

✓ Right

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

zip stops at the shorter string without complaining, so "ab" and "aba" compare only the overlap and report True. Differing lengths can never be anagrams, so the guard has to come first.

Using one counter map and comparing at the end

✗ Wrong

cs, ct = Counter(s), Counter(t)
return cs == ct

✓ Right

counts[ord(a) - ord('a')] += 1
counts[ord(b) - ord('a')] -= 1
return all(c == 0 for c in counts)

It works, but builds two dictionaries and hashes every character twice. Incrementing for one string and decrementing for the other lets a single array end at all zeros exactly when they match.

06

Edge cases

Different lengths

An early length check returns false before any counting.

Same letters, different order

Counting is order-independent, so any rearrangement still cancels to zero.

Repeated letters, e.g. 'aab' vs 'aba'

Counts accumulate per letter, so repeats are tracked exactly and still net to zero.

07

Complexity

Time

O(n)

Space

O(1)

Fixed 26-letter tally regardless of input size.