Group Anagrams
Problem Statement
Given an array of strings strs, group the anagrams together. You may return the groups in any order, and the strings within each group may appear in any order.
Input
An array of lowercase strings strs.
Output
A list of groups, where each group contains strings that are anagrams of one another.
Constraints
- •
1 <= strs.length <= 10^4 - •
0 <= strs[i].length <= 100 - •
strs[i] consists of lowercase English letters
Examples
Example 1
strs = [eat, tea, tan, ate, nat, bat]
[[eat, tea, ate], [tan, nat], [bat]]Example 2
strs = [a]
[[a]]Example 3
strs = [empty string]
[[empty string]]Learning Objectives
- Recognise anagram grouping as a canonical-key hash map problem.
- Build a collision-safe key from either sorted characters or a 26-count signature.
- Use a map from signature to list of words to collect groups incrementally.
- Compare sorted-key simplicity with count-signature performance.
Intuition
Pattern Recognition
The signal is that order inside each word does not matter, only the multiset of characters. Comparing every pair of strings would be expensive, and sorting the entire input array does not directly reveal all groups.
Create a canonical representation for each word so all anagrams produce the same key. That key can be a sorted string or a 26-length count signature. Then a hash map from key to group lets each word go directly to its anagram bucket.
Common mistakes
- ×Using the raw word as the key, which keeps **eat** and **tea** in separate groups.
- ×Building an ambiguous count key such as **111** without separators, which can collide for different count vectors.
- ×Forgetting to create a new list when a signature appears for the first time.
- ×Assuming the output group order must match a specific ordering when the problem allows any order.
Algorithm Explanation
Key idea
Map each word to a canonical signature. For lowercase English letters, count the 26 letters and join the counts with a separator such as # so different count vectors cannot collapse into the same key. Every anagram has the same signature and therefore lands in the same list.
Walkthrough
For strs = [eat, tea, tan, ate, nat, bat], the words eat, tea, and ate all produce the same counts for a, e, and t, so they share one key and one group. The words tan and nat share counts for a, n, and t, so they form another group. bat has a different signature and remains alone.
Algorithm
- Create a hash map from signature string to list of words.
- For each word, build its canonical key.
- If the key is not in the map, create a new empty list for it.
- Append the word to the list for that key.
- Return all map values as the final grouped result.
Solutions
Solution 1: Count signature grouping
Use this when strings are lowercase English letters and you want to avoid sorting each word. The key length is fixed by the alphabet size.
For every word, count its 26 letters and serialize those counts with a plain separator character. The serialized count vector is identical for anagrams and different for non-anagrams.
Step-by-step
- Create groupsBySignature, a map from signature to list of words.
- For each word, fill a 26-entry count array using char - 'a' indexing.
- Build a signature by appending each count followed by #.
- Add the word to the list stored for that signature.
- Return a new list containing every grouped value list from the map.
O(totalChars + 26 * m)
O(totalChars + 26 * m)
m is the number of strings; each word is scanned once and each signature has 26 counts.
Java implementation
Solution 2: Sorted string key
Use this when simplicity matters more than shaving the per-word sorting cost, or when the alphabet is not fixed to lowercase English letters.
Sorting the characters of a word produces a canonical key because anagrams become the same sorted string. The grouping map is then identical to the count-signature approach.
Step-by-step
- Create a map from sorted-character key to list of words.
- Convert each word to a character array and sort it.
- Use the sorted string as the key.
- Append the original word to the group for that key.
- Return all grouped lists from the map.
O(totalChars log L)
O(totalChars)
L is the maximum word length; each word is sorted before insertion into the map.
Java implementation
Dry Run
Sample input
strs = [eat, tea, tan, ate, nat, bat]. Track the canonical count signature and the groups map.
| step | word | signature summary | groups after insertion |
|---|---|---|---|
| 1 | eat | a1 e1 t1 | a1 e1 t1: [eat] |
| 2 | tea | a1 e1 t1 | a1 e1 t1: [eat, tea] |
| 3 | tan | a1 n1 t1 | a1 e1 t1: [eat, tea]; a1 n1 t1: [tan] |
| 4 | ate | a1 e1 t1 | a1 e1 t1: [eat, tea, ate]; a1 n1 t1: [tan] |
| 5 | nat | a1 n1 t1 | a1 e1 t1: [eat, tea, ate]; a1 n1 t1: [tan, nat] |
| 6 | bat | a1 b1 t1 | add a1 b1 t1: [bat] |
Every word is routed by signature, so anagrams meet in the same map entry without pairwise comparisons.
Interview Tips
State the canonical-key principle clearly: anagrams must produce the same key and non-anagrams should not collide. If you use count signatures, mention why separators like # matter. If you use sorted keys, mention the simpler code and the extra sorting factor.
Likely follow-ups
- How would the signature change for Unicode strings or mixed-case input?
- How would you return groups sorted by size or lexicographic order?
- How would you group anagrams from a stream without storing all input first?
- How would you reduce memory if the input contains many repeated identical words?
Similar Problems
Key Takeaways
- Grouping problems usually need a canonical key before the hash map becomes useful.
- For lowercase anagrams, a 26-count signature avoids sorting every word.
- Separators in count signatures prevent ambiguous keys.
- The output order is flexible unless the problem adds ordering requirements.