Canonical key hashing
Map each item to a canonical form; equal forms share a bucket.
Two items are 'the same' iff their keys are equal.
01The intuition
Start with what you would do by hand
Look at the strings abc, bcd, ace, xyz, az. Some of them are "shifts" of each other: bcd is abc with every letter moved one step forward, and xyz is abc moved 23 steps forward. The task is to group strings that are shifts of each other.
By hand you might try to shift one string until it matches another: shift abc by 1, compare with bcd, match. Shift abc by 2, compare with ace, no. Shift by 3, no, and so on for 25 shifts against every other string. For n strings of length k that is about 25 · n2 · k letter comparisons. For 10,000 strings of 10 letters it is 25 billion. Nearly all of that work is re-deriving the same fact: how far apart the letters are.
Build the structure, one piece at a time
Step one: find what does not change when you shift. In abc the gap from a to b is 1 and from b to c is 1. In bcd the gaps are also 1 and 1. In xyz they are 1 and 1 again. Shifting adds the same amount to every letter, so differences between neighbouring letters stay the same. That list of gaps is a canonical form: the one fixed description that every member of the group shares.
Step two: compute that form for each string. Take letters as numbers (a = 0, b = 1, …) and write down the gaps, wrapping around at 26 so that "az" and "ba" are handled: gap = (next − current + 26) mod 26.
Step three: put the forms in a hash map from form to list of strings, the same bucketing machine as frequency counting.
| String | Letters as numbers | Gaps (the key) | Map afterwards |
|---|---|---|---|
| abc | 0, 1, 2 | (1, 1) | {(1,1): [abc]} |
| bcd | 1, 2, 3 | (1, 1) | {(1,1): [abc, bcd]} |
| ace | 0, 2, 4 | (2, 2) | {(1,1): [abc, bcd], (2,2): [ace]} |
| xyz | 23, 24, 25 | (1, 1) | {(1,1): [abc, bcd, xyz], (2,2): [ace]} |
| az | 0, 25 | (25) | …, (25): [az] |
The same recipe works whenever "the same" means "the same after some transformation". Anagrams: the canonical form is the sorted letters. Isomorphic strings (paper and title have the same shape): replace each letter by the position where it first appeared, so both become 0 1 0 2 3. Duplicate subtrees: write each subtree as a bracketed string like (4) or (2(4)()). In every case you ask one question: what stays fixed under the transformation, and how do I write it down so that equal things give equal strings?
Why it is correct
The key must be a true fingerprint: two items get the same key if and only if they belong together. Both directions matter. For shifts: if t is s shifted by d, every letter of t is s's letter plus d, so each gap is
(si+1 + d) − (si + d) = si+1 − si
which is unchanged, so same key. Conversely, if two strings have the same gaps and the same length, choose d as the difference of their first letters; then every later letter also differs by d, because the letters are the first letter plus the running sum of the gaps. So same key means they are shifts. A key that satisfied only one direction would either split a group or merge two groups.
Why it is fast
Each string's key is computed once, in O(k) for a string of k letters, and inserted into the map in about one step. That is O(n · k) overall, a few hundred thousand operations for the 10,000-string example instead of 25 billion. The repeated work of the by-hand method, re-shifting and re-comparing, is gone because the comparison became an equality test on a short key.
How to recognise it in an interview
Cues: "group the strings that are …", "are these two structures the same up to …", "find duplicate sub-structures". The first thing to say: "I will define a canonical key that is identical for everything in a group and different otherwise, then bucket by that key in a hash map." Then spend your effort on the key, because that is where the bugs live: the wrap-around in Group Shifted Strings, mapping both directions in Isomorphic Strings so that "ab" and "aa" are not confused, and including empty children in the string for Find Duplicate Subtrees so that different shapes do not collide.
02The idea in one line
Map each item to a canonical form; equal forms share a bucket.
Reach for it when: Grouping by structure: anagrams, shifted strings, isomorphism, duplicate subtrees.
Cost: O(n·k) time.
03The walk-through, step by step
The video works one example: Group Shifted Strings: 'abc','bcd','xyz' share the key (1,1). These are its captions in order, so you can follow without the video or check a step you missed.
- Shifting every letter keeps the gaps between letters: hash the gaps
- 'abc' → gaps (1,1): new group
- 'bcd' → gaps (1,1): same group as abc
- 'ace' → gaps (2,2): new group
- 'xyz' → gaps (1,1): same group as abc
- 'az' → gaps (25): new group
- 'ba' → gaps (25): same group as az
- 'a' → gaps (·): new group
- 'z' → gaps (·): same group as a
- Equal keys ⇔ same shifted family: four groups
- Build each key in O(k): O(n · k) total
04Asked at Google
7 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.
| Problem | Difficulty | Frequency | Reported |
|---|---|---|---|
| Group Anagrams | Medium | 58 | last 6 months |
| Isomorphic Strings | Easy | 45 | last 6 months |
| Group Shifted Strings | Medium | 35 | last 6 months |
| Find Duplicate Subtrees | Medium | 28 | |
| Word Pattern | Easy | 26 | last 6 months |
| Find and Replace Pattern | Medium | 13 | |
| Equal Row and Column Pairs | Medium | 8 |
05Related patterns
Other patterns in Arrays & Hashing: Hash the complement, Frequency counting, In-place index hashing, Set-start expansion, Seen-set cycle detection.