Group Anagrams
Give every anagram the same canonical key.
Approach
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.
Time complexity
O(n·k)
Space complexity
O(n·k)
Common mistake
Using a mutable list as a dict key — keys must be hashable, so use a tuple or string.
Interactive walkthrough — step through it below, free and without an account
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"]]
Problem
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.
Problem and Goal
Learning goal: Recognize when a collection problem can be solved by grouping items under a shared identity.
Core idea Two words are anagrams exactly when every letter appears the same number of times in both words. We do not need to compare every pair of words. Instead, we compute a canonical description for each word and use that description to locate its bucket in a hash map.
Definition
A canonical key is a representation that is identical for objects considered equivalent. Here, equivalent objects are anagrams.
Algorithm plan
- Create an empty map from canonical keys to lists of words.
- Process each word independently.
- Compute its letter-frequency key and append the word to that key's bucket.
- Return all map values.
Micro-example
eat has counts a=1, e=1, and t=1.
tea has the same counts, so both words select the same bucket.
Pitfalls
- Comparing every pair repeats work and can become quadratic in the number of words.
- A key must preserve all letter counts, not merely the set of letters.
- Empty strings need a valid all-zero key.
Recap
- Anagrams share a letter-count signature.
- A hash map turns that shared signature into a group.
- Each word is processed once.
Problem and Goal
Same letters, same bucket
Words belong together when their canonical keys match. For example, `eat`, `tea`, and `ate` all map to the same frequency signature.
Group by identity instead of comparing every pair.
Canonical Keys and Frequency Maps
Learning goal: Understand why a 26-length count tuple gives every anagram the same key.
Core idea Use an array of 26 counters, one for each lowercase letter. While scanning a word, increment the counter for each character. Two words produce the same tuple if and only if they contain the same multiplicity of every letter, regardless of order.
Key insight
The positions in the tuple are fixed: index 0 represents a, index 1 represents b, and so on through z.
Algorithm plan
- Initialize
count = [0] * 26for the current word. - For each character
ch, incrementcount[ord(ch) - ord('a')]. - Convert the mutable array to a tuple.
- Use that tuple as the dictionary key.
Micro-example
For eat, the nonzero entries are a:1, e:1, and t:1.
For tea, the increments occur in another order, but the final tuple is identical.
Pitfalls
- The tuple must be created after counting finishes.
- A frequency key must include counts, so
{a,e,t}would incorrectly treataetttas equivalent toeat. - Keep the alphabet mapping consistent across all words.
Recap
- A count tuple is order-independent.
- Converting the list to a tuple makes the key hashable.
- Matching tuples identify anagram groups.
Canonical Keys and Frequency Maps
Rearranging letters must not change the key.
`eat` and `tea` match.
Main Approach: Count Instead of Sort
Learning goal: Choose the frequency-tuple implementation when the alphabet is fixed and small.
Core idea
There are two standard canonical forms. Sorting each word produces a canonical string, but sorting costs O(k log k) for a word of length k. Counting letters takes one pass, so the tuple approach costs O(k) per word and reaches the target O(n·k) time.
Why it works
Every word contributes exactly one map lookup and one bucket append after its key is built.
Algorithm plan
- Initialize
groupsas a map from tuple keys to word lists. - For each word, build its 26-counter array.
- Freeze the array as a tuple and call it
key. - Append the word to
groups[key]. - Return the map's bucket values.
Micro-example
tan and nat both create the same tuple with one a, one n, and one t.
Their different spellings therefore lead to one shared bucket.
Pitfalls
- Sorting is correct, but it does not meet the best stated time bound.
- Reusing one counter array across words would mix their frequencies.
- The map should create a fresh bucket when a key appears for the first time.
Recap
- Sorting key: O(n·k log k).
- Count-tuple key: O(n·k).
- Both are correct; the tuple is faster for a fixed alphabet.
Main Approach: Count Instead of Sort
| Key construction | Time | Key type | Best use |
|---|---|---|---|
| Sort each word | O(n·k log k) | String | Simple general-purpose solution |
| Count 26 letters | O(n·k) | Tuple | Fixed lowercase alphabet; target solution |
Walkthrough: Build the Buckets
Learning goal: Trace how each input word becomes a key and joins exactly one bucket.
Core idea
We will process ['eat', 'tea', 'tan', 'ate', 'nat', 'bat'] from left to right. The visualization abbreviates a 26-length tuple by listing only its nonzero counts, such as a1,e1,t1; this is still the same full tuple used by the algorithm.
Algorithm plan
- Start with an empty map.
- Count the current word's letters.
- Convert the counts to an immutable tuple key.
- Append the word to the matching bucket.
- Continue until every word has been placed.
Micro-example
After eat, the map contains a1,e1,t1 → ['eat'].
When tea produces a1,e1,t1, it appends to that existing bucket.
Read the trace
A repeated key means “same anagram class,” not “duplicate input.” Every occurrence is still appended.
Pitfalls
- Do not use the word itself as the key; anagrams would remain separate.
- Do not omit zero positions when implementing the actual tuple.
- Do not sort the displayed shorthand and mistake it for the full count tuple.
Recap
- Each input word causes one key computation.
- Matching keys merge buckets naturally.
- The final map values are the answer.
Walkthrough: Build the Buckets
Processes the exact example from the problem statement and shows bucket updates.
Pitfalls and Edge Cases
Learning goal: Avoid key-type errors and handle unusual but valid inputs safely.
Core idea The frequency counter is naturally mutable because we increment its entries. A dictionary key, however, must be hashable and stable after insertion. Therefore, convert the completed list to a tuple before using it as a key; alternatively, encode the counts into a string.
Common pitfall
Using a mutable list as a dict key fails because lists are unhashable. Use tuple(count) or a carefully constructed string instead.
Algorithm plan
- Build a fresh 26-counter list for every word.
- Finish all increments before creating the key.
- Convert the list to a tuple.
- Let the map create a bucket for unseen keys.
- Append even when the word repeats an existing word.
Micro-example
For an empty word, the key is the all-zero tuple, and every empty word shares that bucket.
For ['a', 'a'], both entries belong in the same bucket, preserving duplicates.
Pitfalls
- A list key raises a hashability error in Python.
- A mutable key changed after insertion would invalidate map lookup behavior.
- Forgetting duplicate occurrences loses input data.
- Assuming all words have length at least one misses the empty-string case.
Recap
- Mutable counters are working data, not final keys.
- Tuples are immutable and hashable.
- Empty strings and duplicates require no special algorithm.
Pitfalls and Edge Cases
Which value is safe to use as a Python dictionary key after counting a word?
Complexity and Wrap-up
Learning goal: Relate the frequency-map implementation to the target complexity and recognize the reusable pattern.
Core idea
Let n be the number of words and k be the maximum word length. Counting 26 lowercase letters takes O(k) time per word, and appending each word takes amortized O(1) time. The resulting total is O(n·k), with O(n·k) space for stored words and their groups.
Algorithm plan
- Define a canonical key for each input item.
- Use a hash map from key to collection.
- Insert each item into its key's collection.
- Return the collections.
Micro-example For six words of length at most three, the algorithm performs a short linear scan per word. The map stores the six original words, so output storage is included in the space bound.
Reusable pattern
Whenever objects need to be grouped by an equivalence rule, search for a compact canonical representation and hash it.
Pitfalls
- Reporting O(n) while ignoring the cost of scanning each word is incomplete.
- Sorting keys change the per-word cost to O(k log k).
- Auxiliary counters are small, but the returned groups still require O(n·k) space in the worst case.
Recap
- Frequency tuple: O(n·k) time.
- Stored groups and keys: O(n·k) space.
- Canonicalization plus hashing is the main transferable technique.
Complexity and Wrap-up
Summarizes the cost of counting keys and storing the grouped output.
Now try it on your own problem
Paste any LeetCode problem — or one of your own — and codebrew builds a walkthrough like this one for it.
Build a lesson from any problem