Appearance
4.4.4 — Group Anagrams
LeetCode 49 · Medium · ★ Blind 75
The problem
Group the strings that are anagrams of each other. Any order is fine.
["eat","tea","tan","ate","nat","bat"]
→ [["eat","tea","ate"], ["tan","nat"], ["bat"]]Up to 10,000 strings, each up to 100 lowercase letters. A string may be empty.
The pattern
Comparing every pair of strings is far too slow. Comparing pairs is what you do when you cannot name the thing that makes two items equal.
Here you can. Give every string a label that is the same for anagrams and different for everything else. Then throw each string into the bucket named by its label, and the buckets are the answer. Nothing ever gets compared.
That label is called a fingerprint, or a canonical form. Choosing it is the whole problem. The map is bookkeeping.
Fingerprint 1 — sort the letters
Every anagram of a word sorts to the same string. "eat", "tea" and "ate" all sort to "aet".
python
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups = defaultdict(list)
for s in strs:
key = ''.join(sorted(s))
groups[key].append(s)
return list(groups.values())ts
function groupAnagrams(strs: string[]): string[][] {
const groups = new Map<string, string[]>();
for (const s of strs) {
const key = [...s].sort().join('');
if (!groups.has(key)) groups.set(key, []);
groups.get(key)!.push(s);
}
return [...groups.values()];
}defaultdict(list) makes an empty list the first time you touch a missing key, so you never write if key not in groups. TypeScript has no equivalent, which is what the extra if line is doing.
sorted(s) returns a list, and a list cannot be a dictionary key in Python. ''.join(...) turns it back into a string, which can. Store the original string in the bucket, not the key.
groups.values() in Python returns a view object rather than a list, so wrap it in list(...).
O(n \cdot k \log k) time for n strings of length k.
Fingerprint 2 — count the letters
Anagrams are defined by counts, not order. So use the counts as the label and skip the sort.
python
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups = defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
groups[tuple(count)].append(s)
return list(groups.values())ts
function groupAnagrams(strs: string[]): string[][] {
const groups = new Map<string, string[]>();
const a = 'a'.charCodeAt(0);
for (const s of strs) {
const count = new Array(26).fill(0);
for (const c of s) count[c.charCodeAt(0) - a]++;
const key = count.join(',');
if (!groups.has(key)) groups.set(key, []);
groups.get(key)!.push(s);
}
return [...groups.values()];
}O(n \cdot k) time — a factor of \log k better.
The two language traps in the key line
Both languages refuse to let you use the count array directly, for different reasons, and only one of them tells you.
Python raises. groups[count] gives TypeError: unhashable type: 'list'. A list can be changed after it is stored, and a key that changes value would leave its entry stranded in the wrong bucket. tuple(count) makes an immutable copy, and that fixes it.
JavaScript stays silent, which is worse. An array is accepted as a Map key, but Map compares keys by identity, not contents. Two arrays holding the same numbers are two different objects, so every string ends up alone in its own group and nothing reports an error. count.join(',') turns it into a string, and strings compare by value.
Keep the comma. Without a separator, [1,11,0] and [11,1,0] both join to "1110" and two unrelated groups silently merge. A count of 11 is easy to reach in a 100-character string, so this is a real bug, not a theoretical one. It is the same delimiter problem that 4.4.6 is entirely about.
Which fingerprint to use
Counting is asymptotically better and wins clearly on long strings. Sorting works for any alphabet, including Unicode, where you cannot allocate a slot per character.
For the 100-character strings here, sorting is often faster in wall-clock time despite the extra \log k, because it runs in tuned C on contiguous memory while the counting loop runs at Python speed. Noticing that the asymptotics and the stopwatch disagree is worth saying out loud.
Edge cases
The empty string sorts to "" and counts to 26 zeros, so it groups with other empty strings. Correct, and no special case needed. Duplicate strings stay as duplicates — you are grouping the inputs, not the distinct values.
Where this goes next
Every one of these is this code with a different fingerprint:
- Group shifted strings —
"abc"and"bcd"match, so the fingerprint is the gaps between consecutive letters, taken modulo 26. - Number of Distinct Islands — two islands match if one can slide onto the other, so the fingerprint is the set of cell offsets from the island's top-left corner. Chapter 4.20.
- Normalising emails, deduplicating listings, detecting copied code — all the same idea in production.
The rule: when a problem says "group things that are equivalent under some rule", write the function that maps equivalent things to the same key. If you cannot write it, you do not yet understand the rule.
What the interviewer will push on
"Why is your key valid?" Two words are anagrams exactly when they have the same letter counts, so they share a key exactly when they are anagrams. A fingerprint that merges too much is wrong, and so is one that separates too much.
"What if the strings are very long?" Counting, not sorting.
"What if the input is Unicode?" The 26-slot array dies. Sort instead, or use a map of character to count and build the key from sorted (char, count) pairs.
"You are using an array as a key — are you sure that works?" Python refuses loudly; JavaScript accepts it and quietly breaks. Say which failure is more dangerous and why.
One thing to volunteer: name the pattern. "This is the canonical-form move — map equivalent items to one representative and the grouping falls out." Then say which fingerprint you picked and why.
Next: 4.4.5 Top K Frequent Elements — count first, then ask a second question of the counts.