Valid Anagram
Decide whether two words use exactly the same letters, the same number of times.
- Frequency counting
Before this, know: Strings and indexes, Hash maps (Map in JavaScript, dict in Python)
You get two words, s and t. Return true if t is an anagram of s, and
false otherwise.
An anagram is a word made by rearranging all the letters of another word,
using each letter exactly once. “listen” and “silent” are anagrams. So are
“anagram” and “nagaram”. “rat” and “car” are not: “rat” has a t, “car” has a c.
A string is a row of characters, so like an array each character has an index starting at 0:
- a0
- n1
- a2
- g3
- r4
- a5
- m6
- n0
- a1
- g2
- a3
- r4
- a5
- m6
The rules that matter:
- Order doesn’t matter, counts do. “aab” and “abb” use the same kinds of letters but not the same amounts, so they’re not anagrams.
- If the lengths differ, the answer is
falsestraight away. - On LeetCode the words contain only lowercase English letters
atoz(remember this, it unlocks a trick later), and can be up to 50,000 letters long.
Those piles are a frequency count: for each letter, how many times it
appears. We’ll store them in a hash map (a Map in JavaScript, a dict in
Python): a structure that stores key → value pairs and finds any key in about
one step. Here the key is a letter and the value is its count.
| letter | count |
|---|---|
| a | 3 |
| n | 1 |
| g | 1 |
| r | 1 |
| m | 1 |
Pause and think
No. Count s: a → 2, b → 1. Count t: a → 1, b → 2. The letters are the
same but the amounts are not. Checking “does every letter of t appear in s?”
isn’t enough; we must compare the counts.
The most direct idea: for each letter of s, scan t for an unused copy of
that letter and cross it off. If we can’t find one, they’re not anagrams. If
every letter finds a partner, they are.
Brute force: cross letters off
s = "rat", t = "car"
- r0
- a1
- t2
- c0
- a1
- r2
- letters scanned
- 3
- answer
- —
- Looking at now
- Matching letter in t
- Just crossed off
- Crossed off earlier
s[0] is "r". Scan t's letters from the start: found an unused "r" at position 2. (3 letters looked at so far.)
Which line is running?
function isAnagram(s, t) { if (s.length !== t.length) return false; const left = t.split(""); // letters of t we haven't used yet for (const ch of s) {Running now: const at = left.indexOf(ch); // scan for a matching letter if (at === -1) return false; left[at] = null; // cross it off so it can't be used twice } return true;}Brute force: cross letters off
function isAnagram(s, t) { if (s.length !== t.length) return false; const left = t.split(""); // letters of t we haven't used yet for (const ch of s) { const at = left.indexOf(ch); // scan for a matching letter if (at === -1) return false; left[at] = null; // cross it off so it can't be used twice } return true;}def is_anagram(s, t): if len(s) != len(t): return False left = list(t) # letters of t we haven't used yet for ch in s: if ch not in left: # scan for a matching letter return False # no unused copy of ch is left left[left.index(ch)] = None # cross it off so it can't be used twice return TrueCrossing off matters: without it, “aab” vs “abb” would match the first a of t
twice.
Each letter of s may scan most of t. With words of length n that’s up to
n × n letter checks. For 7 letters, about 49. For 50,000 letters (LeetCode’s
limit), about 2,500,000,000. We describe this growth with Big-O notation,
a short way of saying how the work grows as the input grows (see
Big-O in 5 minutes). Work that grows like
n × n is O(n²): double the length and
the work goes up four times.
If we sort the letters of both words, anagrams turn into the exact same string: “anagram” and “nagaram” both become “aaagmnr”. Then one comparison answers the question.
Sort and compare
function isAnagram(s, t) { if (s.length !== t.length) return false; return [...s].sort().join("") === [...t].sort().join("");}def is_anagram(s, t): return sorted(s) == sorted(t)Sorting costs about n × log n steps, written O(n log n). For 50,000 letters that’s under a million steps: a huge improvement, and a fine answer to give first in an interview. But we can do it in a single pass, with no sorting.
Both slow approaches are really trying to answer “does each letter appear the same number of times?”. So let’s count directly.
Pattern
Frequency counting
Use it when: the answer depends on how many times each value appears, not on the order.
Signal words
- “anagram”
- “same characters”
- “permutation of”
- “how many times”
- “most frequent”
- “majority”
- If the lengths differ, return
false. - Make an empty hash map
count. - Walk through
s. For each letter, add 1 to its count. - Walk through
t. For each letter, if its count is 0 (or missing),thas a letterscan’t supply: returnfalse. Otherwise subtract 1. - If we get through all of
t, returntrue.
Press Play and watch the counts go up while we walk s (violet) and back
down while we walk t (amber). Then try “rat” vs “car” to see where it fails,
and the two edge cases.
Count with a hash map
s = "anagram", t = "nagaram"
- a0
- n1
- a2
- g3
- r4
- a5
- m6
- n0
- a1
- g2
- a3
- r4
- a5
- m6
| letter | count | |
|---|---|---|
| empty | ||
- walking
- —
- answer
- —
- Looking at now
- Already counted
- Tally went up (from s)
- Tally went down (used by t)
- Letter t can't match
Both words have 7 letters, so they might be anagrams. Make an empty hash map "count": letter → how many of that letter s has given us.
Which line is running?
function isAnagram(s, t) { if (s.length !== t.length) return false;Running now: const count = new Map(); // letter -> how many s has that t hasn't used up for (const ch of s) { count.set(ch, (count.get(ch) ?? 0) + 1); } for (const ch of t) { if (!count.get(ch)) return false; // t has a letter s ran out of count.set(ch, count.get(ch) - 1); } return true;}Why is it safe to return true without checking that every count is 0 at the
end? The lengths are equal, so t takes away exactly as many letters as s put
in. If no count ever went below zero along the way, they must all have landed
on exactly zero.
LeetCode promises only lowercase a to z. That’s just 26 possible keys, so we
can swap the hash map for a plain array of 26 counters. Slot 0 counts a,
slot 1 counts b, …, slot 25 counts z.
To find a letter’s slot we use its character code, the number a computer uses
to store it: 'a' is 97, 'b' is 98, and so on. So code − 97 gives 0 for a,
1 for b, 25 for z.
This version also walks both words at the same time: +1 for s[i], −1 for
t[i]. Slots can dip below zero in the middle; only the final check matters.
Count with an array of 26 slots
s = "anagram", t = "nagaram"
- a0
- n1
- a2
- g3
- r4
- a5
- m6
- n0
- a1
- g2
- a3
- r4
- a5
- m6
- a00
- b01
- c02
- d03
- e04
- f05
- g06
- h07
- i08
- j09
- k010
- l011
- m012
- n013
- o014
- p015
- q016
- r017
- s018
- t019
- u020
- v021
- w022
- x023
- y024
- z025
- answer
- —
- Looking at now
- +1 from s
- −1 from t
- Not zero at the end
- Zero
Make 26 counters, all 0: one slot per letter, 'a' in slot 0 up to 'z' in slot 25. The slot number is the letter's code minus the code of 'a'.
Which line is running?
function isAnagram(s, t) { if (s.length !== t.length) return false;Running now: const count = new Array(26).fill(0); // slot 0 = 'a' ... slot 25 = 'z' for (let i = 0; i < s.length; i++) { count[s.charCodeAt(i) - 97]++; // 97 is the character code of 'a' count[t.charCodeAt(i) - 97]--; } return count.every((c) => c === 0);}26 counters
function isAnagram(s, t) { if (s.length !== t.length) return false; const count = new Array(26).fill(0); // slot 0 = 'a' ... slot 25 = 'z' for (let i = 0; i < s.length; i++) { count[s.charCodeAt(i) - 97]++; // 97 is the character code of 'a' count[t.charCodeAt(i) - 97]--; } return count.every((c) => c === 0);}def is_anagram(s, t): if len(s) != len(t): return False count = [0] * 26 # slot 0 = 'a' ... slot 25 = 'z' for i in range(len(s)): count[ord(s[i]) - ord("a")] += 1 count[ord(t[i]) - ord("a")] -= 1 return all(c == 0 for c in count)The map and the array are the same idea. The array is a little faster in practice (no hashing) and its size never changes. The map works for any characters, including capital letters, digits, accents or emoji, which is LeetCode’s follow-up question.
Here is the hash map version again:
Count with a hash map
function isAnagram(s, t) { if (s.length !== t.length) return false; const count = new Map(); // letter -> how many s has that t hasn't used up for (const ch of s) { count.set(ch, (count.get(ch) ?? 0) + 1); } for (const ch of t) { if (!count.get(ch)) return false; // t has a letter s ran out of count.set(ch, count.get(ch) - 1); } return true;}def is_anagram(s, t): if len(s) != len(t): return False count = {} # letter -> how many s has that t hasn't used up for ch in s: count[ch] = count.get(ch, 0) + 1 for ch in t: if count.get(ch, 0) == 0: return False # t has a letter s ran out of count[ch] -= 1 return TrueJavaScript fits an if and its return on one line, while Python uses two, so
the line numbers sometimes differ. Where they do, we give both.
- Line 1: define the function. (LeetCode writes
var isAnagram = function(s, t)in JavaScript anddef isAnagram(self, s, t)insideclass Solutionin Python.) - Line 2 (JS) / lines 2–3 (Python): different lengths can never be anagrams. Checking this first also makes the shortcut at the end safe.
- Line 3 (JS) / line 4 (Python): an empty map.
new Map()in JS,{}in Python. - Lines 4–5 (JS) / lines 5–6 (Python): count every letter of
s.count.get(ch) ?? 0(JS) andcount.get(ch, 0)(Python) mean “the current count, or 0 if this letter isn’t in the map yet”. Then we store that plus 1. - Line 7: walk through
t. - Line 8 (JS) / lines 8–9 (Python): if the count is 0 or missing,
shas no spare copy of this letter. In JavaScript!count.get(ch)is true for bothundefined(missing) and0. - Line 9 (JS) / line 10 (Python): use one copy up.
- Line 11: every letter of
twas matched. Returntrue.
Let’s trace s = "aab", t = "aba" with the hash map version.
| phase | letter | what happens | count afterwards |
|---|---|---|---|
| walk s | a | a: 0 → 1 | {a: 1} |
| walk s | a | a: 1 → 2 | {a: 2} |
| walk s | b | b: 0 → 1 | {a: 2, b: 1} |
| walk t | a | a > 0, so a: 2 → 1 | {a: 1, b: 1} |
| walk t | b | b > 0, so b: 1 → 0 | {a: 1, b: 0} |
| walk t | a | a > 0, so a: 1 → 0 | {a: 0, b: 0} |
| end | every count is 0: return true | {a: 0, b: 0} |
Compare with t = "abb": at the third letter of t we’d need a b, but its
count is already 0, so we’d return false right there.
Brute force: cross letters off
Time
O(n²)
For each of the n letters of s we may scan all n letters of t.
Space
O(n)
A copy of t's letters so we can cross them off.
Sort and compare
Time
O(n log n)
Sorting each word dominates; the final comparison is n steps.
Space
O(n)
The sorted copies of both words.
Count with a hash map
Time
O(n)
One walk through s and one through t, with about one step per map update.
Space
O(1)
At most 26 keys (lowercase letters), however long the words are. With arbitrary characters it would be O(k) for k different characters.
Array of 26 slots
Time
O(n)
One walk through both words, then 26 checks.
Space
O(1)
Always exactly 26 counters.
What to say out loud, in this order:
- Clarify the alphabet: “Only lowercase a–z? Unicode?” The answer picks between the array and the map.
- Sorting first: “Sort both and compare: O(n log n).”
- Then counting: “Count with a map or a 26-slot array: O(n) time, O(1) space for a fixed alphabet.”
- Mention the length check and why it matters.
Likely follow-up questions:
- “What if the inputs contain Unicode characters?” Use the hash map, not the 26-slot array.
- “What if
sis huge and streamed?” Counting works in one pass; sorting needs everything in memory.
Related problems:
- Group Anagrams (this week): many words at once, grouped by their letters.
- Top K Frequent Elements (this week): frequency counting again, then picking the biggest counts.
- Contains Duplicate (this week): “seen or not” instead of “how many”.
- Permutation in String (week 2): the same counts, inside a sliding window.