Appearance
4.4.4 — Group Anagrams
LeetCode 49 · Medium · ★ Blind 75
The problem
You are given a list of words called strs. Put the words into groups, so that every group holds words that are anagrams of each other. Two words are anagrams when they use exactly the same letters the same number of times, like "eat" and "tea". Return the groups in any order.
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
→ [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
strs = [""] → [[""]]
strs = ["a"] → [["a"]]There can be up to 10,000 words. Each word has up to 100 lowercase letters, and a word may be empty. The order of the groups does not matter, and the order of words inside a group does not matter.
What the problem is really asking
In 4.4.2 you checked whether two words are anagrams. Now you have thousands of words, and you must sort them into piles.
Here is the question that unlocks it. Can you give every word a label, so that two words get the same label exactly when they are anagrams? If you can, you never need to compare words with each other. You just compute each word's label and drop the word into the pile with that label.
A label like this is called a fingerprint. It is one standard version that every equivalent word turns into. Once you have chosen a good fingerprint, the rest of the problem is easy. The map that holds the piles is just bookkeeping.
The brute force, and where it wastes work
Without a fingerprint, you have to compare words in pairs.
python
def groupAnagrams(strs):
used = [False] * len(strs)
groups = []
for i in range(len(strs)):
if used[i]:
continue
group = [strs[i]]
used[i] = True
for j in range(i + 1, len(strs)):
if not used[j] and sorted(strs[i]) == sorted(strs[j]): # anagram test
group.append(strs[j])
used[j] = True
groups.append(group)
return groupsWith n words, this compares up to about \frac{n^2}{2} pairs. For 10,000 words, that is 50 million anagram tests, and each test sorts two words. Far too slow.
The waste in one sentence: it sorts the same word again and again, once for every other word it is compared against, when one label per word would be enough.
The idea
Think about sorting a big pile of Lego bricks. You could pick up each brick and compare it with every brick you have already sorted. Or you could read the brick's type, "red 2×4", and drop it into the box with that name. The second way never compares two bricks. The name on the box is the fingerprint.
For words, there are two good fingerprints.
- Sort the letters. Every anagram of a word sorts to the same string. "eat", "tea" and "ate" all become "aet". Words that are not anagrams sort to different strings.
- Count the letters. Make the 26 counts from Valid Anagram, one per letter. Every anagram has exactly the same 26 counts.
Then keep a hash map from fingerprint to the list of words with that fingerprint. Each word gets its fingerprint computed once and is appended to one list.
Solution 1 — sort the letters
python
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups = defaultdict(list) # (1)
for s in strs: # (2)
key = ''.join(sorted(s)) # (3)
groups[key].append(s) # (4)
return list(groups.values()) # (5)ts
function groupAnagrams(strs: string[]): string[][] {
const groups = new Map<string, string[]>(); // (1)
for (const s of strs) { // (2)
const key = [...s].sort().join(''); // (3)
if (!groups.has(key)) groups.set(key, []); // (4)
groups.get(key)!.push(s);
}
return [...groups.values()]; // (5)
}Line by line
(1) groups = defaultdict(list). A map from fingerprint to a list of words. A defaultdict(list) is a normal dictionary with one extra habit. When you look up a key that is not there yet, it quietly creates an empty list for that key instead of raising an error. That saves us from writing "if this key is new, make an empty list" by hand.
(2) for s in strs. Visit each word once.
(3) key = ''.join(sorted(s)). Build the fingerprint. sorted(s) takes the letters of the word and returns them in alphabetical order, as a list of single letters. For "tea" that is ['a', 'e', 't']. Then ''.join(...) glues the list back into one string, "aet".
Why turn it back into a string? Because a Python list cannot be a dictionary key. A list can be changed after you store it, and a key that changes would leave its entry in the wrong place. A string cannot be changed, so it is a safe key.
(4) groups[key].append(s). Put the original word into the pile named by its fingerprint. We store s, not key, because the answer must contain the real words.
In TypeScript there is no defaultdict. So we write the "make an empty list if the key is new" step ourselves with if (!groups.has(key)) groups.set(key, []), and then push.
(5) return list(groups.values()). The piles are the answer. groups.values() gives the lists, but as a special "view" object, not a real list. Wrapping it in list(...) turns it into the list of lists the judge expects.
Complexity, derived
Let n be the number of words and k the length of the longest word.
Time. For each of the n words, line (3) sorts k letters. Sorting k items takes about k \log k steps. Line (4) hashes a key of length k, which takes k steps, and that is smaller than k \log k. So each word costs O(k \log k), and all n words cost O(n \cdot k \log k).
Space. Every word is stored once in some pile, which is n \cdot k letters. Each pile also has a key of up to k letters. So the space is O(n \cdot k).
Solution 2 — count the letters
Sorting finds the order of the letters, but anagrams only care about counts. So we can use the counts directly as the fingerprint 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 # (1)
for c in s: # (2)
count[ord(c) - ord('a')] += 1
groups[tuple(count)].append(s) # (3)
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); // (1)
for (const c of s) count[c.charCodeAt(0) - a]++; // (2)
const key = count.join(','); // (3)
if (!groups.has(key)) groups.set(key, []);
groups.get(key)!.push(s);
}
return [...groups.values()];
}Line by line
(1) count = [0] * 26. A fresh set of 26 counts for this word. It must be made inside the loop, so every word starts from zero.
(2) Count each letter. ord(c) - ord('a') turns a letter into a slot from 0 to 25, exactly as in Valid Anagram. We add one to that slot.
(3) Use the counts as the key. This line is where both languages set a trap, and they set it in different ways.
- Python will not accept
countitself as a key. You getTypeError: unhashable type: 'list'.tuple(count)makes a copy that can never change, and a tuple is allowed as a key. Python fails loudly, which is good, because you notice at once. - TypeScript and JavaScript do accept an array as a
Mapkey, but they compare array keys by identity, not by contents. Identity means "is this the very same object in memory". Two separate arrays holding the same 26 numbers are two different objects. So every word would land in its own pile, and no error would appear. That silent failure is far more dangerous.count.join(',')turns the counts into a string like"1,0,0,0,1,...", and strings are compared by contents.
Keep the comma in join(','). Without a separator, the counts [1, 11, 0] and [11, 1, 0] would both become the string "1110". Two different words would share a pile. A count of 11 is easy to reach in a 100-letter word, so this is a real bug. The same problem is the whole subject of the next-but-one page, 4.4.6.
Complexity, derived
Time. For each of the n words, line (2) visits k letters once. Building the key from 26 counts takes a fixed 26 steps, which does not grow with the input. So each word costs O(k), and all words cost O(n \cdot k). That is better than Solution 1 by a factor of \log k.
Space. Still O(n \cdot k), because every word is stored. Each key is 26 numbers, so the keys add only O(n).
Trace
Take strs = ["eat", "tea", "bat"] with Solution 2. We only show the letter counts that are not zero.
| Step | Word | Non-zero counts | Pile it joins | Piles after |
|---|---|---|---|---|
| 1 | "eat" | a:1, e:1, t:1 | new pile A | A = ["eat"] |
| 2 | "tea" | a:1, e:1, t:1 | pile A (same counts) | A = ["eat", "tea"] |
| 3 | "bat" | a:1, b:1, t:1 | new pile B | A = ["eat", "tea"], B = ["bat"] |
The answer is [["eat", "tea"], ["bat"]]. No two words were ever compared with each other.
Which fingerprint to choose
Counting is faster in theory, by that factor of \log k. It wins clearly on very long words.
Sorting works for any characters, including Unicode, where you cannot make one slot for every possible character.
There is one more surprise. For short words like the 100-letter limit here, Solution 1 often runs faster in practice. Python's sorted is written in fast, compiled code. The counting loop in Solution 2 runs one Python step at a time, which is slower per step. So the theory and the stopwatch can disagree. Saying that in an interview shows you have actually run code.
Edge cases
- The empty word. It sorts to
""and counts to 26 zeros. All empty words land in the same pile. No special code needed. - Repeated words, such as
["a", "a"]. Both copies go into the same pile, giving[["a", "a"]]. You are grouping the inputs, not removing repeats. - A single word. One pile with one word.
Variations you will meet
Each of these is the same code with a different fingerprint.
- Group Shifted Strings. "abc" and "bcd" belong together because each letter is shifted by the same amount. The fingerprint is the list of gaps between neighbouring letters: for "abc" the gaps are 1 and 1, and for "bcd" they are also 1 and 1. A gap that wraps past
zis counted modulo 26, which means "take the remainder after dividing by 26", so the gap fromztoais 1. - Number of Distinct Islands. Two islands of land on a grid count as the same shape if one can slide onto the other. The fingerprint is the list of each land cell's position measured from the island's first cell. See 4.20.
- Real software does this constantly. Removing duplicate email addresses (by lowercasing them first), or spotting copied code (by stripping spaces and comments first), are the same move.
The general lesson: when a problem says "group things that are equivalent under some rule", write a function that turns equivalent things into the same key. If you cannot write that function, you do not yet understand the rule.
What the interviewer will push on
"Why is your key correct?" They are checking that your fingerprint works in both directions. Two words get the same key when they are anagrams, and only when they are anagrams. A key that merges too much is wrong, and so is a key that splits too much.
"What if the words are very long?" Counting, because it skips the \log k factor of sorting.
"What if the input is Unicode?" The 26 slots no longer work. Sort the letters, or build a map of character to count and make the key from the sorted list of (character, count) pairs.
"You used an array as a key. Does that work?" In Python it refuses with an error. In JavaScript it is accepted and quietly puts every word in its own pile. Explain why the quiet failure is worse.
One thing to volunteer: name the move. "I map every word to one standard form, and the grouping falls out of the map." Then say which fingerprint you chose and why.
Next: 4.4.5 Top K Frequent Elements. We count first, and then ask a second question of the counts.