Grouping With Canonical Keys

Beginner: give equivalent things the same label

The words eat, tea, and ate look different, but they contain the same letters. Imagine sorting a pile of differently written address cards into mail trays. Before filing each card, you rewrite the address in one standard form. Cards that now have the same label belong in the same tray.

A canonical key is that standard label. Sorting each word’s letters works for anagrams:

eat → aet
tea → aet
tan → ant
ate → aet
nat → ant
bat → abt

Once the transformation exists, grouping is ordinary Map insertion:

function groupAnagrams(words: string[]): string[][] {
  const groups = new Map<string, string[]>()

  for (const word of words) {
    const key = [...word].sort().join("")
    const group = groups.get(key) ?? []
    group.push(word)
    groups.set(key, group)
  }

  return [...groups.values()]
}

The invariant is:

After processing the first i words, each map entry contains exactly the processed words whose canonical representation equals that entry’s key.

Worked trace

For ['eat', 'tea', 'tan', 'ate']:

word  key  groups after insertion
eat   aet  aet → [eat]
tea   aet  aet → [eat, tea]
tan   ant  aet → [eat, tea], ant → [tan]
ate   aet  aet → [eat, tea, ate], ant → [tan]

The output group order may follow insertion order. If the prompt accepts groups in any order, do not add sorting just to imitate one displayed example.

Intermediate: derive the key from equivalence

Do not begin with “I should use a Map.” Begin with the relationship:

Which differences should be ignored, and which information must be preserved?

Examples include normalizing case for case-insensitive groups, encoding adjacent differences for shifted strings, or serializing a tree’s shape and values. The exact key changes; the workflow remains stable:

1. Define when two inputs belong together.
2. Transform every input into a deterministic representation.
3. Verify the representation preserves all relevant information.
4. Use that representation as the Map key.

Advanced: frequency signatures

Sorting a word of length k costs O(k log k). If inputs contain only lowercase English letters, count the 26 possible characters instead:

function frequencyKey(word: string): string {
  const counts = Array<number>(26).fill(0)
  for (const character of word) {
    counts[character.charCodeAt(0) - 97] += 1
  }
  return counts.join("#")
}

For abb, the meaningful portion is 1#2#0#...; for bab, it is identical. The delimiter is important. Concatenating raw counts could make distinct vectors ambiguous: [1, 11] and [11, 1] both resemble 111 without boundaries.

For n words with maximum length k:

• Sorted keys take O(n · k log k) time.
• Fixed-alphabet frequency keys take O(n · k) time when 26 is treated as constant.
• Both store the grouped output and keys, so total storage still grows with the input.

The frequency approach assumes a known alphabet. Sorting is more general and often the best first interview answer because it is easier to implement and prove. Optimize only when the constraints or interviewer make the tradeoff relevant.

Common failure modes

• Using the original input as the key, so equivalent forms never meet.
• Designing a lossy key that groups non-equivalent inputs together.
• Using an ambiguous serialization without separators.
• Assuming lowercase ASCII when the contract allows broader characters.
• Optimizing the key before defining the equivalence rule.