Grouping With Canonical Keys

Canonical Keys: Give Equivalent Inputs the Same Representation

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.

Choose a Key Based on What Makes Inputs Equivalent

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

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

The answer determines the key. The following examples use different transformations, but they are all solving the same problem: remove differences that do not matter while preserving every difference that does.

Example 1: ignore capitalization

Suppose names belong together when they contain the same characters in the same order, regardless of uppercase or lowercase spelling:

"Ada"  → "ada"
"ADA"  → "ada"
"ada"  → "ada"
"Adan" → "adan"

Calling toLowerCase() is normalization: it converts several acceptable forms into one standard form. Capitalization is deliberately discarded because the grouping rule says it is irrelevant. Character order and length remain, so "Ada" and "Adan" do not accidentally meet.

const key = name.toLowerCase()

Normalization must match the problem statement. Do not remove spaces, punctuation, or accents unless the rules also say those differences should be ignored.

Example 2: preserve a shifting pattern

Now suppose two lowercase strings belong together when one can be produced by shifting every letter by the same distance around the alphabet:

abc → bcd → xyz
ace → bdf
az  → ba

abc and bcd use different letters, but both move forward by one position between neighbors. Record those adjacent movements instead of the letters themselves:

abc → length 3, differences [1, 1]
bcd → length 3, differences [1, 1]
xyz → length 3, differences [1, 1]

ace → length 3, differences [2, 2]
bdf → length 3, differences [2, 2]

Wrapping from z back to a needs modular arithmetic. For az, the movement from a to z is 25. For ba, ordinary subtraction gives -1, but adding 26 and taking the remainder also gives 25. They therefore receive the same pattern key.

function shiftedStringKey(word: string): string {
  const differences: number[] = []

  for (let i = 1; i < word.length; i += 1) {
    const previous = word.charCodeAt(i - 1) - 97
    const current = word.charCodeAt(i) - 97
    differences.push((current - previous + 26) % 26)
  }

  return `${word.length}|${differences.join(",")}`
}

The length is included so an empty string and a one-character string cannot share the same empty difference list. The key works because adding the same shift to both letters does not change the distance between them. If two equal-length strings have all the same adjacent distances, choosing the shift for their first letters also aligns every later letter.

Example 3: preserve a tree’s missing branches

A tree key must represent both node values and structure. Consider these two trees:

first       second
   1           1
  /             \
 2               2

Writing only the encountered values gives 1,2 for both trees, which incorrectly says they are equivalent. A serialization turns the entire structure into a deterministic string. Include a marker such as # for every missing child:

first  → 1,2,#,#,#
second → 1,#,2,#,#

type TreeNode = {
  value: number
  left: TreeNode | null
  right: TreeNode | null
}

function treeKey(node: TreeNode | null): string {
  if (node === null) return "#"
  return `${node.value},${treeKey(node.left)},${treeKey(node.right)}`
}

The traversal order is always node, left subtree, right subtree. Values preserve what each node contains, and # markers preserve where children are absent. Two trees get the same key exactly when the relevant values and positions match.

The workflow, made explicit

1. Define belonging. Finish the sentence “Two inputs are equivalent when…”
2. Choose what to discard. Case, starting position, or object identity may be noise.
3. Choose what to preserve. Order, frequency, length, gaps, values, or shape may determine whether inputs truly belong together.
4. Build one deterministic representation. The same input must always produce the same key.
5. Try to break the key. Test an equivalent pair that looks different and a non-equivalent pair that looks similar.
6. Use the proven representation as the Map key. The Map performs the grouping; the key defines which items are allowed to meet.

Anagram Keys: Encode Character Counts Instead of Sorting

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("#")
}

character.charCodeAt(0) returns a numeric code. Lowercase a has code 97, so subtracting 97 maps the fixed alphabet into array positions:

character  code  index
a           97     0
b           98     1
c           99     2
...
z          122    25

For abb, the array begins [1, 2, 0, ...]: one a, two bs, and no cs. bab produces the same counts even though its order differs. abc begins [1, 1, 1, ...], so it stays in another group.

The delimiter in counts.join("#") is important. Without boundaries, [1, 11] and [11, 1] would both look like 111. With delimiters they become 1#11 and 11#1, which cannot collide for that reason.

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.