Group a list of words so every anagram lands in the same bucket — the trick is hashing each word by a 26-length count signature instead of sorting, giving O(n·k) instead of O(n·k log k).
Given an array of strings, group words that are anagrams of each other. Output order inside groups and order of groups both don't matter.
Example: ["eat","tea","tan","ate","nat","bat"] → [["eat","tea","ate"],["tan","nat"],["bat"]]. eat, tea, and ate are all rearrangements of the letters a,e,t; tan and nat share a,n,t; bat is alone.
number[26] of zeros; for each character, increment freq[ch.charCodeAt(0) - 97]. Serialize with freq.join(',') — this gives a unique, collision-free string key.map.get(key) ?? [], push the word, re-set.Array.from(map.values()).charCodeAt(0) - 97 idiom. Don't reach for .sort() in an interview without mentioning the faster alternative.Both share the same O(n·k) space for storing n words of max length k. The count key is a constant factor win: for a fixed-size alphabet the inner loop runs exactly 26 iterations regardless of k, while sort is genuinely super-linear.
eat, tea, tan, ate, nat, bat. We will compute a 26-length count signature for each word and bucket words by that key.function groupAnagrams(strs: string[]): string[][] {
const map = new Map<string, string[]>();
for (const word of strs) {
const key = countKey(word); // O(k) — no sorting
const bucket = map.get(key) ?? [];
bucket.push(word);
map.set(key, bucket);
}
return Array.from(map.values());
}
/** Build a 26-length frequency signature. Faster than sorting: O(k) vs O(k log k). */
function countKey(word: string): string {
const freq = new Array<number>(26).fill(0);
for (const ch of word) {
freq[ch.charCodeAt(0) - 97]++;
}
return freq.join(',');
}Map<string, string[]> because the canonical key is a string and we need to accumulate word arrays per key. A plain object would also work, but Map is idiomatic for non-literal keys.map.get(key) ?? [] creates the bucket on first use — we must re-set it afterward so the new array reference is stored back in the map.Array.from(map.values()) returns all groups. Iteration order matches insertion order in a JS Map, so the first word's group comes first — matching LeetCode's acceptance behavior, though order is not required.number[26] zeros array per word ensures no cross-word contamination. Subtracting 97 maps 'a'→0, 'z'→25. freq.join(',') produces a unique string like 1,0,0,...,1,0,1 that equals the sorted form of any permutation.join. O(n·k) space for the map (dominated by storing every word). If k is bounded (e.g. ≤ 100), the 26-slot array makes the inner loop a constant and join always produces a 26-segment string of fixed maximum length.Map<string, number> keyed on the character instead of a fixed-size array.Int32Array(26), sort the entries, and serialize. Or accept the tiny allocation: in practice the GC handles it fine.map.values() and call .sort() on each bucket — O(n·k log k) extra work.| "group / cluster words that are anagrams" | frequency-count key → hash map buckets |
| "same letters, different order" equality | canonical signature (count or sort) |
| grouping strings by some invariant | map<invariant, string[]> |
| need faster than O(k log k) per word | count array → O(k) key |
function groupAnagrams(strs: string[]): string[][] {
const map = new Map<string, string[]>();
for (const word of strs) {
const key = countKey(word);
const bucket = map.get(key) ?? [];
bucket.push(word);
map.set(key, bucket);
}
return Array.from(map.values());
}
function countKey(word: string): string {
const freq = new Array<number>(26).fill(0);
for (const ch of word) freq[ch.charCodeAt(0) - 97]++;
return freq.join(',');
}1,0,0,...,1,0,1. Any permutation of the same letters produces the identical string."eat"?["eat","tea","tan","ate","nat","bat"], how many buckets does the map contain?