Group Anagrams
Group Anagrams: given an array of strings, group together all the strings that are anagrams of each other. The groups may be returned in any order.
- 1 <= strs.length <= 10⁴
- 0 <= strs[i].length <= 100
- strs[i] consists of lowercase English letters.
Intuition
Anagrams are the same multiset of letters wearing different orders. So invent a label that ignores order — sort the letters, or count them — and every anagram of a word produces the identical label. Then the problem collapses into ordinary bucketing: a dictionary from label to list.
Whenever you must group items by an equivalence relation, stop comparing pairs and start computing a canonical key. The pattern is: derive a value that is identical for equivalent items, then hash on it. It turns O(n²) comparison into O(n) bucketing, and it shows up again in isomorphic strings, grouping shifted strings, and deduplicating structurally equal trees.
Approach
Before reading on: you need a test for 'these two words are anagrams' that does not involve comparing them to each other. What single value could you compute from one word alone that every anagram of it would also produce? Aim for O(n · k).
The question is really 'what makes two words the same?'
Comparing every pair of strings to test anagram-ness is O(n²) comparisons, each costing O(k) — far too slow. Turn it around: instead of comparing words to each other, map each word to a canonical form that all its anagrams share. If eat, tea, and ate all reduce to the same key, grouping is just a matter of dropping each word into the bucket its key names. This converts a pairwise-comparison problem into a single-pass hashing problem.
Sorted letters as the canonical key
Sorting a word's characters is the simplest canonical form: eat → aet, tea → aet, ate → aet. Use that sorted string as a dictionary key whose value is the list of original words. One pass over n words, each costing O(k log k) to sort, gives O(n · k log k) time overall. It is short, obviously correct, and the version most interviewers expect first.
A 26-count tuple removes the log factor
Because the alphabet is fixed at 26 lowercase letters, you can build the key by counting instead of sorting: a tuple of 26 integers recording how many times each letter appears. Two words are anagrams exactly when their count tuples are equal. Building a count costs O(k) rather than O(k log k), so total time drops to O(n · k). The tuple must be immutable to be hashable — a Python tuple, or a joined string like 1#0#2#... in other languages. Prefer this when the words are long enough that the sort cost bites.
Solution & live demo
Common pitfalls
Using a list as the dictionary key
groups[counts].append(word)
groups[tuple(counts)].append(word)
Lists are mutable and therefore unhashable — Python raises TypeError: unhashable type: 'list'. Convert to a tuple (or a joined string) so the key is immutable and hashes correctly.
Sorting the whole list of words first
strs.sort() # then scan for neighbouring anagrams
for word in strs:
groups[key(word)].append(word)Sorting the array orders words lexicographically, which does not place anagrams next to each other — ate and eat are separated by everything starting with b, c, d. It is the letters inside each word that must be sorted, not the collection.
Building the key with a plain string concat of counts
key = ''.join(str(c) for c in counts)
key = tuple(counts) # or '#'.join(map(str, counts))
Without a separator the counts run together ambiguously: a word with counts 1,11 and one with 11,1 both produce 111, silently merging two different groups. Use a tuple, or join with a delimiter.
Edge cases
Its key is the empty string (or an all-zero count), so it forms its own valid group.
One key, one bucket, one group of one — no special casing needed.
Every word gets a distinct key, so the answer is n groups of size 1.
Identical words share a key and land in the same group; duplicates are kept, not collapsed.