ASAPUtils
The signal
“Group these together” plus an equivalence relation (being anagrams). The instinct is to compare every pair — that’s O(n²) and it’s the wrong shape. When a problem asks you to group by an equivalence, the move is to find a canonical key: one value that every member of a group produces and nothing else does. Then a hash map does the grouping for free.
Approach ladder
1. Brute force — O(n² · m)
For each word, scan all the groups formed so far and check whether it’s an anagram of that group’s representative. Correct, and quadratic.
2. What is it wasting?
It re-derives “are these anagrams?” over and over. If each word could just announce which group it belongs to, no comparison would be needed at all.
3. The insight
Anagrams are exactly the strings with the same multiset of characters. So compute something that depends only on that multiset:
- Sorted characters —
"eat","tea","ate"all become"aet". - Count signature — a 26-length count vector, e.g.
"1#0#0#0#1#…#1#…".
Either is a canonical key. Bucket by it in one pass.
4. Optimal
unordered_map<string, vector<string>> groups;
for (auto& s : strs) {
string key = s;
sort(key.begin(), key.end());
groups[key].push_back(s);
}
vector<vector<string>> res;
for (auto& [k, v] : groups) res.push_back(v);
return res;
function groupAnagrams(strs) {
const groups = new Map();
for (const s of strs) {
const key = [...s].sort().join('');
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(s);
}
return [...groups.values()];
}
The O(m) key, worth knowing for long words:
const count = new Array(26).fill(0);
for (const c of s) count[c.charCodeAt(0) - 97]++;
const key = count.join('#'); // '#' separates so 1,11 ≠ 11,1
That '#' matters. Without a separator, counts of [1, 11] and [11, 1] both stringify to
"111" and two different groups silently merge.
Complexity
- Time O(n · m log m) with a sorted key, O(n · m) with a count key, for n words of length m.
- Space O(n · m) — every word is stored once in a bucket, plus the keys.
Traps
- No separator in the count key. Silent wrong answers, and painful to debug.
- Using a plain object in JavaScript and then hitting inherited keys like
constructor. UseMap. - Sorting the whole input instead of each word’s characters. Different thing entirely.
- Assuming output order matters. It doesn’t here — say so, and don’t waste time sorting.
Blank re-solve prompt
Given a list of words, group the anagrams together, in one pass. Then do it again with a key you can compute in O(m) rather than O(m log m).