Group Anagrams
Group Anagrams is LeetCode 49 (Medium). Given an array of strings strs, group anagrams together and return the groups in any order. Two words are anagrams when one is a rearrangement of the other's letters, like eat, tea and ate.
- Up to 10⁴ words, each up to 100 lowercase English letters (possibly empty).
- Comparing every pair of words is O(n²) comparisons; the target is one pass that gives each word a key.
- 1 <= strs.length <= 10⁴
- 0 <= strs[i].length <= 100
- strs[i] consists of lowercase English letters.
Intuition
Anagrams have the same letters in a different order, so the trick is a key that ignores order: every anagram of a word must produce the same key, and words that are not anagrams must not.
Counting letters gives exactly that. eat, tea and ate each have one a, one e and one t, so their 26 counts are equal, while tan differs. Use the counts as a hash map key and append each word to its key's list. The groups form on their own, without comparing any two words.
Grouping items that are "the same up to order" means computing one standard key per item and grouping by it, instead of comparing pairs. The same idea solves Valid Anagram (compare two keys), Group Shifted Strings, and Find All Anagrams in a String (counts over a sliding window).
Approach
Before reading on: what could you compute from eat alone that tea and ate would also produce, but tan would not? How would you use it to put every word in its group in one pass?
Two ways to solve it
Count the 26 letters of each word and use the counts as the key.
- Work: one pass over each word's letters.
- Key: 26 numbers, whatever the word length.
- Limit: relies on a fixed alphabet.
The fastest choice for lowercase English words.
Sort the letters of each word, so eat, tea and ate all become aet, and use that string as the key.
- Work: a sort per word, k log k.
- Key: a string as long as the word.
- Limit: none on the alphabet.
Shorter to write, and works for any characters.
Counting skips the sort inside every word, so it wins on time; the steps, code and live demo follow it. The sorted-key code, the version most people write first, comes after the demo.
Map keys to lists
Create a hash map from key to list of words. Python's defaultdict(list) and Java's computeIfAbsent create the list the first time a key appears, so a new key needs no special case.
Count the letters of each word
For each word, fill 26 counters, one per letter: counts[ch - 'a'] += 1. That is O(k) for a word of length k. Two words are anagrams exactly when all 26 counts match.
Turn the counts into a key
A hash map key must not change, so a Python list will not do: use tuple(counts). C++ can use a 26-character string with one character per count; Java's Arrays.toString(counts) gives a string with separators.
Append each word and return
Append the word to the list under its key, then return all the lists. Each word is counted once and looked up once, so the whole run is O(n · k) for n words of length up to k.
Group Anagrams solution in Python | C++ | Java
eat letter by letter and add 1 to that letter's counter. The order of the letters makes no difference to the counts, which is exactly why anagrams end up with the same key.eat starts a new group under this key.tea: a 1, e 1, t 1.tea joins the group without being compared to any other word.tan: a 1, n 1, t 1.tan starts a new group under this key.ate: a 1, e 1, t 1.ate joins the group without being compared to any other word.nat: a 1, n 1, t 1.nat joins the group without being compared to any other word.bat: a 1, b 1, t 1.bat starts a new group under this key.abc letter by letter and add 1 to that letter's counter. The order of the letters makes no difference to the counts, which is exactly why anagrams end up with the same key.abc starts a new group under this key.bca: a 1, b 1, c 1.bca joins the group without being compared to any other word.xyz: x 1, y 1, z 1.xyz starts a new group under this key.Sorted-letters key
Sorting a word's letters gives the same string for every anagram of it, so that sorted string is the key. The rest is identical: append each word under its key and return the lists.
Common pitfalls
Using a list as the dictionary key
groups[counts].append(word)
groups[tuple(counts)].append(word)
Lists can change, so Python refuses to hash them and raises TypeError: unhashable type: 'list'. A tuple holds the same counts and can be a key.
Sorting the list of words instead of each word
strs.sort() # then look for neighbouring anagrams
for word in strs:
groups[key(word)].append(word)Sorting the list orders words alphabetically, which does not put anagrams next to each other: ate and eat end up far apart. It is the letters inside each word that need a fixed order.
Joining counts without a separator
key = ''.join(str(c) for c in counts)
key = tuple(counts) # or '#'.join(map(str, counts))
Without a separator the numbers run together: counts 1, 11 and 11, 1 both become 111, so two different groups merge. Use a tuple, or join with a delimiter.
Edge cases
[""]All 26 counts are 0. That is a valid key, so the answer is [[""]].
["ab", "ab"]Both copies share a key and both stay in the group: [["ab", "ab"]]. Nothing is removed.
Complexity
Group Anagrams FAQ
How is it written in Python?
Use defaultdict(list). For each word, build a key, either the tuple of its 26 letter counts or ''.join(sorted(word)), and append the word under it. Return list(groups.values()).