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.

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

python

▶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

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.

06

Complexity

Time

O(n)

Space

O(1)

Fixed 26-letter tally regardless of input size.