L40 · DP VIII — String DP / Edit Distance

Series: LeetCode — From Basics to Interview-Ready · Session 40 / 65 · Phase 2 · Dynamic programming

Why this session exists

Edit Distance is the canonical two-string DP. Everything else in this family is a variation on it. Once the grid is in your hands — rows indexed by prefixes of the first string, columns by prefixes of the second, one cell per pair of prefixes — you stop solving individual problems and start filling in a form you already know.

That is the actual claim of this session, and it is worth being explicit about why it holds. Every two-string problem asks the same underlying question: given that I have consumed the first i characters of a and the first j characters of b, what is the answer for that pair of prefixes? The answer for the full strings is the bottom-right corner. The recurrence differs — sometimes you take a minimum, sometimes you sum, sometimes you take an OR — but the shape of the grid and the direction of dependency do not.

The reason people find these hard is that they try to think about the whole strings at once. You cannot. The only way in is to fix the last character of each prefix and ask a small number of local questions: do they match, and if not, what single edit could I have made? That is a bounded question with three answers, and three answers means three table lookups.

I want you to leave this session able to draw an empty grid, label the axes, fill the first row and first column with the base cases, and write the recurrence — before you have thought about the problem at all. The problem then only tells you what goes inside the recurrence.

Blank-file warm-up

Five minutes, empty file, no notes. Write dp[i][j] over prefixes of both strings for Edit Distance:

1. Declare the table with the correct dimensions.
2. Fill row 0 and column 0 with the correct base cases, and be able to say in words what each means.
3. Write the match branch and the three-way mismatch branch.

If you get the dimensions right but the base cases wrong, that is the most common outcome and it is diagnostic: it means you know the shape but not the semantics. Say out loud what dp[i][0] means before you assign it a value.

Pattern anatomy

The shape that summons this pattern: two sequences, and an answer that depends on aligning them. Not one string with a window — that is L07 through L12. Two strings, both variable, and the operation you are counting or minimising consumes a character from one or both of them.

The invariant is a definition, and stating it precisely is 80% of the work:

dp[i][j] = the answer for a[0:i] against b[0:j] — the first i characters of a and the first j characters of b.

Note carefully: i is a count, not an index. dp[i][j] uses characters a[i-1] and b[j-1] as its last characters. That single off-by-one is where most of the bugs in this family live, and the fix is to always write the table 1-indexed with an extra row and column for the empty prefix.

Dependencies flow from the top-left. dp[i][j] reads dp[i-1][j-1] (diagonal), dp[i-1][j] (above), and dp[i][j-1] (left). Because of that, a plain row-major double loop is always a valid fill order.

def edit_distance(a: str, b: str) -> int:
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
 
    # base: turning a[0:i] into "" costs i deletions
    for i in range(n + 1):
        dp[i][0] = i
    # base: turning "" into b[0:j] costs j insertions
    for j in range(m + 1):
        dp[0][j] = j
 
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]        # free: last chars align
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j - 1],              # replace a[i-1] with b[j-1]
                    dp[i - 1][j],                  # delete a[i-1]
                    dp[i][j - 1],                  # insert b[j-1]
                )
    return dp[n][m]

Read the three mismatch branches as three questions about what you did to the last character:

• Replace — I paired a[i-1] with b[j-1] and paid 1 to make them equal. Both prefixes shrink: diagonal.
• Delete — I removed a[i-1] entirely. Only a shrinks: from above.
• Insert — I inserted b[j-1] at the end of a. Only b's obligation shrinks: from the left.

Every two-string DP is these same three moves with different costs attached. Learn the geometry — diagonal, up, left — and the specific problem only tells you which moves are legal and what they cost.

The cue

You are looking at a two-string DP when the statement contains these tells:

1. Two strings named in the input, both with variable length. One string plus a pattern of fixed structure is usually something else. Two genuinely free strings with lengths in the hundreds or low thousands is a grid.
2. Constraints around 500 to 2000 per string. That is the fingerprint of an O(n·m) intended solution. 1000 × 1000 is a million cells — comfortable. If both strings could be 10^5, a quadratic grid is out and the intended answer is something else entirely.
3. The words "transform", "convert", "minimum operations", "how many ways to form", or "is s3 an interleaving of". All of these are asking about an alignment between the two inputs.
4. The operations consume characters one at a time from the front or back. Insert, delete, replace, match, skip. If a legal move can jump an arbitrary distance, it is not this pattern.
5. A subsequence relationship rather than a substring one. "Subsequence" almost always means grid DP; "substring" often means sliding window or a suffix structure.

The strongest single tell is tell 2 combined with tell 1. Two strings, both up to a thousand characters, and a question about relating them: build the grid before you have finished reading the problem.

Guided solve

Edit Distance — given word1 and word2, return the minimum number of insert, delete, or replace operations to convert word1 into word2.

Start by naming the subproblem out loud, because if you skip this step you will fumble the base cases. "Let dp[i][j] be the minimum number of operations to convert the first i characters of word1 into the first j characters of word2."

Now the base cases follow mechanically from that sentence rather than from intuition:

• dp[i][0] — convert i characters into nothing. Only deletions can do that, one per character, so the value is i.
• dp[0][j] — convert nothing into j characters. Only insertions, so the value is j.
• dp[0][0] is 0, which both formulas already give.

Then the recurrence. Fix i and j, both at least 1, and look only at the last characters a[i-1] and b[j-1].

If they are equal, there is nothing to pay. Any optimal edit sequence can be rearranged so those two characters are matched against each other for free, so dp[i][j] = dp[i-1][j-1]. This is not obvious and it is worth stating why: if an optimal solution deleted a[i-1] instead, you could always swap that deletion for the free match without increasing the cost.

If they differ, one of exactly three things happened to a[i-1] in the optimal solution — it was replaced, it was deleted, or b[j-1] was inserted after it. Each costs 1 plus the cost of the smaller subproblem, so take the minimum of the three.

Trace a = "horse", b = "ros" on the first two rows to convince yourself. Row 0 is [0,1,2,3]. For row 1 (a prefix is "h"): dp[1][0] = 1. dp[1][1] compares 'h' and 'r' — mismatch, so 1 + min(dp[0][0]=0, dp[0][1]=1, dp[1][0]=1) = 1. Correct: replace h with r. The final answer for the full strings is 3.

Solo timed

Fifteen minutes each, timer running, no editorial until it fires.

• Distinct Subsequences — count how many distinct subsequences of s equal t. Same grid, but you are summing rather than minimising, and the base case for the empty t is not zero. Ask yourself what dp[i][0] should mean when the answer is a count.
• Interleaving String — decide whether s3 is formed by interleaving s1 and s2. The grid is boolean and i + j is fixed by the position in s3, so you never need a third dimension. Work out what that means before you code.

Common failure modes

Index versus count confusion. Writing a[i] instead of a[i-1] inside a loop that runs i from 1 to n. This produces an off-by-one that survives some tests and fails others, and it is by far the most frequent bug in this family. Discipline: the moment you allocate a table of size (n+1) × (m+1), promise yourself that i is a count and the character is at i-1.

Wrong base case for counting problems. In Edit Distance, dp[0][j] = j. In Distinct Subsequences, dp[i][0] = 1 — there is exactly one way to form the empty string from anything, namely by taking nothing. Blindly copying the Edit Distance base cases into a counting problem gives zero everywhere and a silent wrong answer.

Taking min when the problem wants max or a sum. The grid geometry is identical, so the code compiles and runs and gives plausible-looking numbers. Say aloud what the cell means before writing the combine step.

Forgetting the free-match branch. If you write only the three-way minimum and drop the equality check, you get a valid but wrong recurrence that always overpays by the number of matching characters. Test with two identical strings — the answer must be 0.

Complexity

Time: O(n·m). There are (n+1)(m+1) cells and each is computed once from at most three already-computed neighbours, doing constant work. No cell is recomputed because the loop order guarantees dependencies are filled first.

Space: O(n·m) for the full table, reducible to O(min(n, m)) with the rolling-array form. The reduction is possible precisely because the recurrence reaches back exactly one row and one column — no cell depends on anything two rows up.

For the standard constraints of these problems, both strings capped around 500 to 1000, the full table is roughly a million cells and runs in well under a second in Python. Reach for the optimisation only when the numbers demand it.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Edit Distance enters the queue at whatever the blank-file attempt earned, not at what you achieved after reading this page. The queue tracks retrieval, not eventual understanding.