Problem. Given strings s and t, return True if t is an anagram of s: the same letters with the same
counts, in any order.
s = "listen", t = "silent" → True
s = "rat", t = "car" → False
ML context. "Same multiset, any order" is the bag-of-words idea: two documents with the same token counts look identical to a bag-of-words model. Count vectors (histograms) are also how you compare label distributions between a training and a serving set, and how you deduplicate records whose fields arrive in a different order.
The lesson: the right representation makes the comparison trivial. Order is noise here; counts are the signal.
1. Step 1: Clarify
| Question | Answer | Why it matters |
|---|---|---|
| Which characters? | Lowercase a–z (for now) | A fixed alphabet allows a 26-slot array |
| Case and spaces significant? | Yes, compare as given | Normalising is a separate choice |
| Lengths? | Up to 5 × 10⁴ | Rules out anything factorial or quadratic |
| Different lengths? | Then False immediately |
A free O(1) early exit |
2. Step 2: Brute force
The most literal reading: "is t one of the rearrangements of s?" Generate every permutation and compare.
from itertools import permutations
def is_anagram_perm(s, t):
if len(s) != len(t):
return False
return any("".join(p) == t for p in permutations(s)) # n! permutations
assert is_anagram_perm("abc", "cab")
assert not is_anagram_perm("rat", "car")
print("permutation brute force works, but only for tiny strings: O(n! · n)")
O(n! · n) time. At n = 12 that's already about 5.7 × 10⁹ operations; at n = 5 × 10⁴ it's unthinkable.
A slightly better brute force: for each character of s, find and remove one matching character from t.
def is_anagram_remove(s, t):
if len(s) != len(t):
return False
pool = list(t)
for ch in s:
if ch not in pool: # O(n) search
return False
pool.remove(ch) # O(n) shift
return True
assert is_anagram_remove("listen", "silent")
assert not is_anagram_remove("aab", "abb")
print("match-and-remove works: O(n²) time, O(n) space")
O(n²) time: at n = 5 × 10⁴ about 2.5 × 10⁹ steps. Still too slow, so optimise.
3. Step 3: Optimise: find a canonical form
First principles. Two strings are anagrams exactly when they have the same canonical form: one representation that forgets order but keeps everything else. There are two natural ones.
Optimisation A: sort both strings
Sorting puts letters in a fixed order, so anagrams become equal strings.
def is_anagram_sort(s, t):
return len(s) == len(t) and sorted(s) == sorted(t)
assert is_anagram_sort("listen", "silent")
assert not is_anagram_sort("rat", "car")
print("sort version: O(n log n) time, O(n) space for the sorted copies")
O(n log n) time, O(n) space. Simple, and it works for any characters. But sorting does more work than needed: we don't care about the order of letters at all, only how many of each.
Optimisation B: count with a fixed-size array
With the alphabet fixed to a–z, a list of 26 counters is the canonical form. Add 1 for each letter of s,
subtract 1 for each letter of t; anagrams leave every counter at zero.
import random
import string
def is_anagram(s, t):
if len(s) != len(t):
return False
counts = [0] * 26 # fixed size: O(1) space
for a, b in zip(s, t):
counts[ord(a) - ord("a")] += 1
counts[ord(b) - ord("a")] -= 1
return all(c == 0 for c in counts)
def reference(s, t):
return sorted(s) == sorted(t)
assert is_anagram("listen", "silent")
assert not is_anagram("rat", "car")
assert is_anagram("", "")
rng = random.Random(16)
for _ in range(1000):
s = "".join(rng.choice("abcde") for _ in range(rng.randint(0, 10)))
t = list(s)
rng.shuffle(t)
if rng.random() < 0.5 and t:
t[rng.randrange(len(t))] = rng.choice(string.ascii_lowercase) # maybe break it
t = "".join(t)
assert is_anagram(s, t) == reference(s, t)
print("26-slot count array: O(n) time, O(1) space, matches sorting on 1,000 cases")
- Time: O(n): one pass, plus 26 checks.
- Space: O(1): 26 counters, however long the strings are. ("O(alphabet)" is the honest way to say it.)
- Why one array, not two: incrementing for
sand decrementing fortcompares the two histograms as you build them, so a single final check suffices.
Quick check
Why is the 26-slot counting array O(1) space even for strings of length 10⁶?
Show the answer
B. Its size depends only on the alphabet (26), not on the input length; it's really O(alphabet), which is constant once the alphabet is fixed — Space is measured against the input size n; a fixed 26-slot array doesn't grow with n.
4. When the constraints change
Change A: the strings contain any Unicode character
A 26-slot array no longer fits (there are over a million code points). Switch the counter to a hash map: same idea, O(n) time, O(distinct characters) space.
from collections import Counter
def is_anagram_unicode(s, t):
return len(s) == len(t) and Counter(s) == Counter(t)
assert is_anagram_unicode("débruit", "tiburdé")
assert is_anagram_unicode("नमस्ते", "स्तेनम")
assert not is_anagram_unicode("ab", "aa")
print("Counter version handles any characters: O(n) time, O(distinct) space")
A subtle trap worth naming in an interview: "é" can be one code point or "e" plus a combining accent. If the input
may mix both, normalise first (unicodedata.normalize("NFC", s)), or anagrams can look different.
Change B: group many words into anagram families
Given a list of words, group the anagrams together. Comparing every pair is O(m² · k) for m words of length k. Instead, compute each word's signature (its canonical form) once and use it as a dictionary key.
from collections import defaultdict
def group_anagrams(words):
groups = defaultdict(list)
for w in words:
counts = [0] * 26
for ch in w:
counts[ord(ch) - ord("a")] += 1
groups[tuple(counts)].append(w) # the count tuple is hashable: O(k) per word
return list(groups.values())
result = group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
assert sorted(sorted(g) for g in result) == [["ate", "eat", "tea"], ["bat"], ["nat", "tan"]]
print("signature grouping: O(m · k) time instead of O(m² · k)")
The key choice is a mini trade-off: "".join(sorted(w)) costs O(k log k) per word and is short; the count tuple costs
O(k + 26) and wins for long words. That's the same sort-versus-count decision as the main problem.
Change C: the second string arrives as a stream
Build the counts for s first, then decrement as each character of t arrives. Stop as soon as a count goes
negative: t has used a letter more often than s has it. O(1) memory per character, early exit for free.
def is_anagram_stream(s, t_stream):
counts = [0] * 26
for ch in s:
counts[ord(ch) - ord("a")] += 1
remaining = len(s)
for ch in t_stream:
i = ord(ch) - ord("a")
counts[i] -= 1
if counts[i] < 0:
return False # t has too many of this letter: stop now
remaining -= 1
return remaining == 0
assert is_anagram_stream("listen", iter("silent"))
assert not is_anagram_stream("listen", iter("silents"))
assert not is_anagram_stream("listen", iter("sile"))
print("streaming check works, with an early exit")
The full table
| If the constraint becomes… | Best approach | Time | Space |
|---|---|---|---|
| Any characters, simplest code | Sort both | O(n log n) | O(n) |
| Lowercase a–z | 26-slot count array | O(n) | O(1) |
| Unicode text | Counter (hash map), normalise first | O(n) | O(distinct) |
| Group m words of length k | Signature → dictionary | O(m · k) | O(m · k) |
| One string arrives as a stream | Count s, decrement on arrival, early exit |
O(n) | O(1) |
| Compare two large documents as bags of words | Token Counter per document | O(n) | O(vocabulary) |
Quick check
You need to group 10⁵ words into anagram families. Which approach scales?
Show the answer
A. Compute each word's canonical signature (sorted letters or a count tuple) once and use it as a dictionary key: one pass over the words — Pairwise checks are O(m²); a signature reduces grouping to one hash lookup per word.
5. Saying it out loud
"Trying permutations is factorial and match-and-remove is O(n²). Anagrams are exactly the strings with the same canonical form, so I can sort both, O(n log n), or, since the alphabet is a–z, keep 26 counters: add for s, subtract for t, and check they're all zero. That's O(n) time and O(1) space. For Unicode I'd use a Counter; to group many words I'd use the count tuple as a dictionary key."
Check yourself
- What is a "canonical form", and what are the two canonical forms used here?
- Why is the 26-slot array O(1) space?
- Why does incrementing for
sand decrementing fortneed only one final check? - What changes for Unicode input, and what normalisation trap should you mention?
- How do you group anagrams without comparing every pair?
- How does the streaming version exit early?
Answers
- A representation that is equal for exactly the strings you want to treat as equal; here, the sorted string and the letter-count vector.
- Its size depends on the alphabet (26), not on n.
- The array holds count(s) − count(t) for each letter, so the strings match exactly when every entry is zero.
- Replace the array with a hash map; normalise (e.g. NFC) because the same visible character can have different code point sequences.
- Use each word's signature (sorted letters or count tuple) as a dictionary key: one pass, O(m · k).
- After counting
s, decrement for each arriving character and returnFalseas soon as any count goes negative.