Two-sequence DP (LCS / edit distance)

39 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

Turn the word "horse" into "ros" using the fewest edits, where one edit inserts a letter, deletes a letter, or replaces a letter. By hand: replace h with r (rorse), delete r (rose), delete e (ros). Three edits. Could two work? "horse" has five letters and "ros" three, so at least two deletions are needed, and after any two deletions of "horse" the remaining three letters are not "ros". So three is the answer, but that argument was special to this case.

In general you cannot try all edit sequences; their number grows exponentially with the word lengths. The trick is to compare only prefixes, and to notice that the answer for two prefixes depends on the answers for three slightly shorter pairs of prefixes.

Build the structure, one piece at a time

Piece one: a table with one row per prefix of the first word (including the empty prefix) and one column per prefix of the second. dp[i][j] will be the fewest edits turning the first i letters of "horse" into the first j letters of "ros".

Piece two: the edges. Turning i letters into nothing costs i deletions, so dp[i][0] = i; turning nothing into j letters costs j insertions, so dp[0][j] = j.

Piece three: the inside. Look at the last letters of the two prefixes. If they are equal, they need no edit and dp[i][j] = dp[i − 1][j − 1], the diagonal. If not, the last edit is one of three: delete the last letter of the first word (dp[i − 1][j], from above), insert the last letter of the second (dp[i][j − 1], from the left), or replace one with the other (dp[i − 1][j − 1], diagonal). Each costs one edit:

dp[i][j] = 1 + min( up, left, diagonal )

Row o, column o: the letters match, so copy the diagonal, 1. Row e, column s: no match, 1 + min(2, 4, 2) = 3. The bottom-right corner is the answer, 3.

Why it is correct

The invariant: every filled cell holds the true minimum for its pair of prefixes. The edges are right by counting. For an inside cell, consider the best edit sequence for the two prefixes and look at how it treats the last letter of the first prefix and the last letter of the second: the options are exactly match, delete, insert or replace, and in each case what remains is a best sequence for one of the three smaller pairs, which are already correct. The formula takes the cheapest option, so the cell is correct.

Longest common subsequence is the same table with a different rule: match adds 1 to the diagonal, otherwise take the max of up and left.

Why it is fast

work = (n + 1)(m + 1) cells × constant, memory two rows if rolled

Two words of 1,000 letters cost a million cell updates; trying edit sequences would never finish.

How to recognise it in an interview

Cues: two strings or two sequences, "minimum edits", "longest common", "minimum deletions to make equal", "is one an interleaving of the others". The first thing to say: "a table over prefixes of both strings; match takes the diagonal, otherwise the best neighbour." Edit Distance is the example above. Longest Common Subsequence uses the max rule. Delete Operation for Two Strings is LCS in disguise: delete everything outside the common subsequence, so the answer is n + m − 2·LCS.

02The idea in one line

dp[i][j] compares prefixes; match takes the diagonal, else the best neighbour.

Reach for it when: LCS, edit distance, distinct subsequences, delete operation, interleaving.

Cost: O(nm) time.

03The walk-through, step by step

The video works one example: Edit Distance 'horse' → 'ros'. These are its captions in order, so you can follow without the video or check a step you missed.

1. Match → take the diagonal; else 1 + min(delete ↑, insert ←, replace ↖)
2. Base row and column: turning a prefix into empty costs its length
3. Row 'h': dp[1][1] = 1 + min(1, 1, 0) = 1
4. Row 'o': dp[2][1] = 1 + min(1, 2, 1) = 2
5. Row 'r': dp[3][1] = diagonal 2 (match 'r')
6. Row 's': dp[4][2] = 1 + min(2, 3, 2) = 3
7. Row 'e': dp[5][1] = 1 + min(3, 5, 4) = 4
8. dp[5][3] = 3: replace h→r, delete r, delete e
9. Fill |s|·|t| cells, each in O(1): O(n·m)

04Asked at Google

8 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), 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, DP over sorted keys (chains).