Group Anagrams
Group words that are rearrangements of each other by giving every anagram family the same canonical key
Problem Statement
Given an array of strings, group the anagrams together. Two words are anagrams if one is a rearrangement of the other's letters. Return the groups in any order.
Input: ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
Input: [""]
Output: [[""]]Intuition
The naive plan — compare every word with every other word to test anagram-ness — is O(n² × k) and gets tangled quickly.
The key insight
Stop comparing words to each other. Instead, give each word a canonical form: a value that is identical for all anagrams and different for everything else.
Then grouping is trivial — a hash map keyed by that canonical form does all the work in one pass.
Two canonical forms work:
1. The sorted letters. "eat", "tea" and "ate" all sort to "aet". Anagrams have the same multiset of letters, so sorting always produces the same string.
2. The letter-count signature. "eat" → one a, one e, one t → the tuple (1,0,0,0,1,0,…,1,…) over 26 slots. Anagrams have identical counts by definition.
Sorting is shorter to write; counting is asymptotically faster because it skips the log k factor.
Real-world analogy
Sorting mail into pigeonholes. You do not compare each letter against every other letter — you read the postcode (the canonical key) and drop it into the matching slot. Everything sharing a postcode ends up together automatically.
Watch it run
Approach
For each word, compute its canonical key
Sorted characters, or a 26-slot count signature.
Append the original word under that key
Store the original, not the key — the output must contain the real words.
Solution
from collections import defaultdict
def group_anagrams(strs: list[str]) -> list[list[str]]:
"""Group words that are rearrangements of one another."""
groups: defaultdict[str, list[str]] = defaultdict(list)
for word in strs:
key = "".join(sorted(word)) # anagrams share this exact key
groups[key].append(word)
return list(groups.values())The counting version, which avoids the O(k log k) sort:
def group_anagrams_counting(strs: list[str]) -> list[list[str]]:
groups: defaultdict[tuple[int, ...], list[str]] = defaultdict(list)
for word in strs:
counts = [0] * 26
for char in word:
counts[ord(char) - ord("a")] += 1
groups[tuple(counts)].append(word) # tuples are hashable, lists are not
return list(groups.values())Two subtle bugs to avoid
Python: a list cannot be a dictionary key — it is mutable and therefore unhashable. Convert the count array to a tuple first.
TypeScript: building the key with counts.join('') is broken. Counts of [1, 11] and [11, 1] both stringify to "111". Use a separator like '#', or pad each count to a fixed width.
Complexity Analysis
Time Complexity
O(n × k log k)
Space Complexity
O(n × k)
Where n is the number of words and k is the maximum word length.
- Time (sorting keys) —
O(k log k)to sort each ofnwords. - Time (counting keys) —
O(n × k), since building a 26-slot signature is linear in the word. This is strictly better, and the gap widens for long words. - Space — every word is stored once in the output, plus the keys.
Edge Cases
Related Problems
- Valid Anagram — the two-word version of the same canonical-form idea
- Two Sum — hash maps turning search into lookup
- Top K Frequent Elements — building a count map, then ranking it