Valid Anagram
Two strings are anagrams iff their character counts match.
Letter Count Trace
Problem
Given two strings, decide whether one can be rearranged to form the other without adding, removing, or changing any characters. The order may differ, but every character must appear the same number of times in both strings.
Examples
Input: s = "listen", t = "silent"
Output: true
Input: s = "rat", t = "car"
Output: false
The Goal
Return True if t is a rearrangement of s: the same letters, each used the same number of times. Otherwise return False.
listen and silent are anagrams. rat and car aren't: one has a t, the other a c.
Order doesn't matter, only counts, so counts are what the solution keeps.
Compare counts, not positions
Rearranging a string moves its letters but never changes how many of each there are.
Same length and the same count for every letter means an anagram.
Key Idea: Add for s, Subtract for t
Keep one counter per letter, count = [0] * 26.
Every letter of s adds one to its counter. Every letter of t takes one away. If the strings are anagrams, each subtraction cancels an addition and every counter ends at 0.
A counter left at anything else names a letter that one string has more of.
Rearranging letters leaves the counts alone.
listen and silent: one each of e, i, l, n, s, t
The Algorithm
Check the lengths first. Different lengths can't be anagrams.
if len(s) != len(t):
return False
count = [0] * 26
for c in s:
count[ord(c) - ord("a")] += 1
for c in t:
count[ord(c) - ord("a")] -= 1
return all(x == 0 for x in count)Check every counter, not the total. A +1 on one letter and a -1 on another add up to 0 too.
| Approach | Time | Space | When |
|---|---|---|---|
| 26 counters | O(n) | O(1) | Lowercase a to z |
| Sort both strings | O(n log n) | O(n) | Simple, but slower |
| Hash map of counts | O(n) | O(k) for k distinct characters | Any alphabet |
Walkthrough
Run it on listen and silent.
Both have 6 letters, so counting starts. The pass over listen sets six counters to 1. The pass over silent takes each back to 0, in a different order. Every counter ends at 0, so the answer is True.
Try aab and abb on the stage. The lengths match, but a ends at 1 and b at -1.
Checkpoint · predict the next step
Step 5 of 15 on the stage: s[2] is 's': count['s'] goes up to 1.
c on "s" (index 2) · t = ["s", "i", "l", "e", "n", "t"] · count = {"i": 1, "l": 1, "s": 1} · len(s) 6 · len(t) 6
Pitfalls
- Comparing letters position by position checks the order, which an anagram is allowed to change.
- Checking which letters appear misses repeats:
aabandabbuse the same letters. - Check every counter at the end. A total of 0 can hide a +1 and a -1.
- The 26 counters assume lowercase a to z. For any other alphabet, count in a hash map.
s = "aab" and t = "ab". What should happen first?
Complexity
After the length check, each string is read once: O(n) time for strings of length n.
The counter array has 26 slots however long the strings get, so extra space is O(1). A hash map over a bigger alphabet needs a slot per distinct character.
Count each string once
- Length checkDifferent lengths return at once.O(1)
- Count sOne add per letter.dominantO(n)
- Count tOne subtract per letter.dominantO(n)
- Check 26 countersThe alphabet is fixed.O(1)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n) | 10 | 100 | 1K | 10K |
Two passes and 26 counters.
In short
Count characters in the first string, then decrement for the second; if every count ends at zero (and lengths match), they're anagrams. A fixed-size array of 26 counts is ideal for lowercase input. Sorting both strings also works but is O(n log n).
Common mistake
Forgetting to check lengths first — differing lengths can never be anagrams and save you the count.