Group Anagrams

Given an array of strings, group the anagrams together. (LC 49)

The recipe

Say before you type: "Two strings are anagrams iff they're equal after sorting — so the sorted string is a canonical key, and grouping is just a map from key to bucket."

1. For each string, compute its canonical form: sort the characters.
2. Use that as a map key; push the original string into the key's bucket.
3. Return the buckets.

The code

function groupAnagrams(strs: string[]): string[][] {
  const groups = new Map<string, string[]>();
  for (const s of strs) {
    const key = s.split('').sort().join(''); // canonical form
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key)!.push(s);
  }
  return [...groups.values()];
}

Why this shape

The deep idea is canonicalization: when "equivalent" doesn't mean "equal," design a transformation under which equivalence becomes equality, then let a hash map collide the equivalents together. "eat", "tea", "ate" all sort to "aet" — one bucket, zero pairwise comparisons.

The brute force compares every pair (O(n²) comparisons); the canonical key eliminates comparison entirely. This move generalizes far past anagrams: normalizing tags, deduplicating records, grouping rotated strings — any time the interviewer says "treat these as the same."

Complexity

	Cost	Because
Time	O(n · k log k)	n strings, each sorted at k log k (k = max string length)
Space	O(n · k)	Every string is stored in some bucket, plus the keys

The follow-up to expect: "can you avoid the sort?" Yes — a character-count key. Count each letter into a 26-slot array and join it into a string like 1#0#0#…; building it is O(k), taking the total to O(n · k). Use a separator (or fixed-width counts), because raw concatenated counts collide (1,11 vs 11,1).

Traps

• Storing the sorted string in the bucket instead of the original — the output must contain the inputs as given.
• The counting-key collision above, if you go for the O(n · k) version and get cute with the key format.
• In TypeScript, remember .sort() on a string requires the split/join dance — strings are immutable.

The pattern this trains

Canonical keys. The same trick powers the tag-normalization phase of the tag registry practical problem — free-text input, canonical identity underneath.