DP over sorted keys (chains)

45 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Words: a, b, ba, bca, bda, bdca. Word X is a predecessor of word Y if adding exactly one letter somewhere in X gives Y. A chain is a sequence where each word is a predecessor of the next, such as a → ba → bda → bdca. How long is the longest chain?

By hand you would pick a word and try to extend it forwards and backwards, then pick another word, and so on. With six words it is manageable. With 1,000 words every word has to be compared with every other to see which pairs are predecessor and successor, 500,000 pairs, and then you still have to search for the longest route through those pairs, which is a longest-path search and branches badly.

Build the structure, one piece at a time

First observation: a predecessor is always exactly one letter shorter. So if you sort the words by length, every predecessor of a word comes before it in the sorted order. Second observation: instead of asking "which words are one letter longer than me", ask each word "which words are one letter shorter than me", by deleting each of its letters in turn and looking the result up in a set. A word of length L has only L such candidates.

Now keep one number per word: chain[w] = the longest chain that ends at w. Walk the sorted list:

The longest value is 4: a → ba → bda → bdca. The structure is a dictionary from word to best chain length, filled in length order so every lookup already has its final value.

Why it is correct

The invariant: when word w is processed, every shorter word already holds its true longest chain. The longest chain ending at w is either w alone, or some chain ending at a predecessor p followed by w. The best such chain is 1 + the best chain ending at the best predecessor, and every predecessor of w is one of the L deletions, all shorter and therefore final. So chain[w] = 1 + max over existing deletions of chain[deletion] is exact, and the invariant extends to w. Words of equal length never affect each other, so their order among themselves does not matter.

chain[w] = 1 + max( 0, max over p = w with one letter removed, p in the set, of chain[p] )

Why it is fast

Sorting n words costs O(n log n). Each word of length L tries L deletions, and building each deletion string costs O(L), so a word costs O(L²) and all words cost O(n · L²), with L at most 16 in the usual problem. For 1,000 words that is about 250,000 cheap steps, against 500,000 pairwise comparisons plus a longest-path search. The win comes from looking downwards (deletions) rather than comparing every pair.

How to recognise it in an interview

Cues: a "comes before" relation that only runs from smaller to larger (shorter string, smaller number, smaller envelope), and "longest chain" or "largest subset where every pair is related". Say: I will sort by the size key so predecessors are already solved, then each item extends the best predecessor it can find. Longest String Chain is this example. Largest Divisible Subset sorts numbers and extends from the largest earlier divisor. Longest Arithmetic Subsequence keys the table by (index, difference).

02The idea in one line

Sort by size; dp[item] extends from the best smaller item it can follow.

Reach for it when: Longest string chain, largest divisible subset, longest arithmetic subsequence.

Cost: O(n · k) time.

03The walk-through, step by step

The video works one example: Longest String Chain on [a, b, ba, bca, bda, bdca]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Sort by length: every predecessor of a word is already final when we reach it
2. 'a': no shorter word by deleting one char, chain = 1
3. 'b': no shorter word by deleting one char, chain = 1
4. 'ba' → drop a char → a, b; chain = 1 + best of them = 2
5. 'bca' → drop a char → ba; chain = 1 + best of them = 3
6. 'bda' → drop a char → ba; chain = 1 + best of them = 3
7. 'bdca' → drop a char → bca, bda; chain = 1 + best of them = 4
8. Longest chain = 4: a → ba → bda → bdca
9. Sort once, then n words × L deletions: O(n log n + n·L²)

04Asked at Google

6 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.

05Related patterns

Other patterns in Dynamic Programming: 1-D linear DP, Kadane (best ending here), Longest increasing subsequence, Grid path DP, 0/1 knapsack (subset sum), Unbounded knapsack (coin change), Two-sequence DP (LCS / edit distance), Wildcard / regex matching DP, Palindromes: expand or table, Prefix segmentation DP, Interval DP (last operation), State-machine DP (stocks), Bitmask DP over subsets, Memoised DFS (top-down), Digit DP, Game DP (minimax on a range), Counting ways with modulo.