Valid Anagram
Valid Anagram: return true if t is an anagram of s — the same letters with the same counts, in any order.
- 1 <= s.length, t.length <= 5 * 10⁴
- s and t consist of lowercase English letters.
Intuition
Valid anagram checks whether two strings contain the same characters with the same frequencies. Order is irrelevant, which is the entire definition. Two approaches solve it, and the trade-off between them is the lesson. Sorting both strings and comparing is the shortest correct answer. Anagrams sort to identical sequences, so one comparison settles it — O(n log n) with O(1) or O(n) space depending on whether the language sorts in place. Counting is faster: - Tally each character in the first string, then decrement while scanning the second; the strings are anagrams exactly when every count returns to zero. A single count array serves both passes, which is neater than building two and comparing them. An early exit on unequal lengths is worth taking first — different lengths can never be anagrams, and the check costs nothing. That length check also guards the counting approach. Without it, a shorter second string leaves positive counts that a naive "no negative counts" test would miss. With lowercase English letters only, a fixed 26-element array beats a hash map: no hashing, no allocation, and genuinely O(1) space. The stated follow-up asks about Unicode. A fixed array no longer works, since the alphabet is unbounded — a hash map is required, and the space becomes O(k) for the distinct characters present. Worth naming, since it is the one change that matters. Counting gives O(n) time and O(1) space for the fixed alphabet, against sorting's O(n log n).
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.
Approach
Before reading on: price up what sorting first costs here, then ask what makes it safe to discard one end without checking it against everything. Aim for O(n) time and O(1) space.
Check lengths first
Different lengths can never be anagrams, and the test costs nothing. It also guards the counting approach against a short second string.
Consider sorting
Anagrams sort to identical sequences, so sorting both and comparing settles it. O(n log n) — the shortest correct answer.
Count with one array
Increment for the first string and decrement for the second. A single array serves both passes, avoiding a second comparison step.
Verify every count is zero
The strings are anagrams exactly when all counts return to zero. Any non-zero entry means a frequency mismatch.
Use a fixed array for lowercase
With only 26 letters, a fixed array beats a hash map — no hashing, no allocation, genuinely O(1) space.
Switch to a map for Unicode
The follow-up's unbounded alphabet breaks the fixed array. A hash map is required, making the space O(k) for the distinct characters present.
Cost of the approaches
Counting is O(n) time and O(1) space for a fixed alphabet; sorting is O(n log n).
Solution & live demo
Common pitfalls
Sorting both strings
return sorted(s) == sorted(t)
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
counts = [0] * 26 for a, b in zip(s, t): ...
if len(s) != len(t):
return Falsezip 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
cs, ct = Counter(s), Counter(t) return cs == ct
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.
Edge cases
An early length check returns false before any counting.
Counting is order-independent, so any rearrangement still cancels to zero.
Counts accumulate per letter, so repeats are tracked exactly and still net to zero.