Group Anagrams
Give every anagram the same canonical key.
Grouping by Letter Counts
Problem
Given a list of lowercase words, place words with identical letter compositions into the same group. The order of the groups and the words inside each group does not matter, as long as every anagram appears together and no word is lost.
Examples
Input: ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
Input: ["abc", "bca", "xyz"]
Output: [["abc", "bca"], ["xyz"]]
The Goal
Given a list of words, group together the ones that are anagrams of each other. The groups can come back in any order.
For ["eat", "tea", "tan", "ate", "nat", "bat"], the groups are [eat, tea, ate], [tan, nat] and [bat].
Comparing every pair of words is slow. Instead, give each word a key that all its anagrams share.
Same letters, same key
Anagrams have the same count of every letter. Use those counts as a hash map key, and the groups form on their own.
Group by a shared key instead of comparing pairs.
Key Idea: Letter Counts as the Key
Count a word's letters into 26 slots, one per letter. eat and tea both get one a, one e and one t, so their counts match.
Turn the counts into a tuple. A list can't be a dictionary key, but a tuple can.
Then append each word to groups[key]. The first word with a key starts its group, and every anagram after it joins.
Rearranging letters can't change the key.
eat and tea match.
The Algorithm
groups = defaultdict(list)
for word in strs:
count = [0] * 26
for c in word:
count[ord(c) - ord("a")] += 1
key = tuple(count)
groups[key].append(word)
return list(groups.values())defaultdict(list) starts an empty group the first time a key shows up. Sorting each word's letters also makes a key anagrams share, but costs O(k log k) per word of length k, against O(k) for counting.
| Key | Time per word | Key type |
|---|---|---|
| Sort the letters | O(k log k) | String |
| Count the letters | O(k) | Tuple of 26 counts |
Walkthrough
Run it on the six words.
eat starts a group. tea has the same counts, so it joins. tan has an n where eat has an e, so it starts a second group. ate and nat join the groups they match, and bat starts a third.
The stage writes each key as the letters a word has, like a1 e1 t1. The code's key is all 26 counts, zeros included.
Checkpoint · predict the next step
Step 4 of 14 on the stage: Count the letters of "tea": its key is a1 e1 t1.
word on "tea" (index 1) · groups = {"a1 e1 t1": ["eat"]} · key a1 e1 t1
Pitfalls
- Make a fresh count for each word. Reusing one mixes the words together.
- A list can't be a key. Use
tuple(count). - Repeated words each go in:
["eat", "eat"]gives one group with both. - An empty word is valid. Its key is all zeros, and every empty word shares it.
Which value can be a dictionary key after counting a word?
Complexity
With n words of at most k letters, each word is counted once in O(k) and appended once. That's O(n·k) time.
The groups hold every word, and each key is 26 counts, so space is O(n·k). Sorting each word instead costs O(n·k log k) time.
Count each word once
- Count each word's lettersk letters per word.O(n·k)
- Look up and appendOne per word, on average.O(n)
- Store the groupsEvery word, once.O(n·k)
Each word is read once, and its key is found in constant time.
In short
Anagrams share a canonical form — either the sorted string or a 26-length count tuple. Use that form as a hash-map key and append each word to its bucket. The count-tuple key gives O(n·k) versus O(n·k log k) for sorting.
Common mistake
Using a mutable list as a dict key — keys must be hashable, so use a tuple or string.