DP VIII — String DP / Edit Distance

Review boundary and corrected contracts

The edit-distance state covers prefixes; empty-prefix costs are lengths, unlike counting subsequences whose empty target has one construction. A full table simplifies edit reconstruction but is not mathematically mandatory: divide-and-conquer reconstruction exists. Working-space bounds exclude the output edits.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Own the two-string DP table. Write the Edit Distance recurrence from memory, then derive Distinct Subsequences and Interleaving String as variations of the same grid.

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

Prerequisites. L33–L35 (state definition, recurrence, memo to table). You should be comfortable declaring a 2D table and filling it in dependency order. No string-algorithm background needed.

Watch first

Optional resources retained from the original lesson; video availability and contents were not rechecked in this review. The worked explanations below are self-contained.

• Edit Distance — Dynamic Programming — Leetcode 72 — NeetCode.
• Edit Distance Between 2 Strings — The Levenshtein Distance — Back To Back SWE.
• Longest Common Subsequence — Leetcode 1143 — NeetCode.

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. The prefix-alignment problems in this lesson ask a shared 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 state meaning, legal transitions and base cases must all be derived anew; changing min to sum or OR alone is not sufficient.

The reason people find these hard is that they try to think about the whole strings at once. You cannot. For unit-cost Edit Distance, a useful 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 derive the recurrence from the allowed operations. The grid is a starting hypothesis, not a substitute for reading the problem.

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.

These three moves describe unit-cost Edit Distance. Related prefix DPs may omit moves or jump more than one column (for example, skipping a character-and-star pair in regex matching). Keep the prefix-state idea, but derive the legal transitions.

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. A pattern can also index a grid, as in regex matching. Two free strings alone do not prove that a quadratic alignment DP is appropriate.
2. Constraints around 500 to 2000 per string. That makes O(n·m) worth considering. 1000 × 1000 is a million interior cells; actual time and memory limits still matter. 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. A move that consumes several characters changes the predecessor offsets and may require more state.
5. A subsequence relationship rather than a substring one. LCS uses a prefix grid, but testing whether one fixed string is a subsequence of another only needs two pointers. The requested output matters as much as the noun.

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: consider a prefix grid, then verify its state and transitions against the complete 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, matching them gives candidate D = dp[i-1][j-1] for free. Neither delete nor insert can beat D: appending one target character changes edit distance by at most 1, so dp[i-1][j] >= D-1; similarly dp[i][j-1] >= D-1. Adding the operation cost makes both candidates at least D. Thus the diagonal is optimal for this unit-cost contract; no arbitrary single deletion needs to be swapped in an existing script.

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.

Space optimisation: the recurrence only reaches back one row, so you can keep two rows instead of the full grid. Put the shorter string on the column axis to get O(min(n, m)) working space (including empty-prefix cells). Do this only after the two-dimensional version is written and correct, and say why you are doing it. The one trap: when you overwrite in place with a single row you destroy dp[i-1][j-1] before you read it, so you must stash the diagonal value in a temporary before assigning.

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.

Worked answers — counting and interleaving

For the LCS comparison, let L[i][j] be the length of a longest common subsequence of the two prefixes. Empty-prefix entries are 0. Matching last characters give L[i-1][j-1]+1; otherwise take max(L[i-1][j], L[i][j-1]) by skipping one unmatched endpoint. This is not Edit Distance with only the min operator replaced: its paid transitions and base cases have changed. For "abc" and "ac", the length is 2, and deletion-only reconciliation costs 3+2-2×2=1.

For Distinct Subsequences, let dp[i][j] count index selections from s[:i] spelling t[:j]. Skipping s[i-1] contributes dp[i-1][j]; using it contributes dp[i-1][j-1] only when the last characters match. These cases are disjoint. Seed dp[i][0]=1 and dp[0][j]=0 for positive j. Thus "rabbbit" has three index selections spelling "rabbit", even though the resulting string is the same.

def distinct_subsequences(s: str, t: str) -> int:
    dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
    for i in range(len(s) + 1):
        dp[i][0] = 1
    for i in range(1, len(s) + 1):
        for j in range(1, len(t) + 1):
            dp[i][j] = dp[i - 1][j]
            if s[i - 1] == t[j - 1]:
                dp[i][j] += dp[i - 1][j - 1]
    return dp[-1][-1]
 
assert distinct_subsequences("rabbbit", "rabbit") == 3
assert distinct_subsequences("", "") == 1

For Interleaving String, first require len(s3)=len(s1)+len(s2). Let dp[i][j] mean the two prefixes can form s3[:i+j], preserving each input's order. The last character comes either from s1 (the cell above) or from s2 (the cell left), and must match s3[i+j-1]. There is no diagonal transition: one output character consumes one input character, not two.

def is_interleave(s1: str, s2: str, s3: str) -> bool:
    if len(s3) != len(s1) + len(s2):
        return False
    dp = [[False] * (len(s2) + 1) for _ in range(len(s1) + 1)]
    dp[0][0] = True
    for i in range(len(s1) + 1):
        for j in range(len(s2) + 1):
            if i:
                dp[i][j] |= dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]
            if j:
                dp[i][j] |= dp[i][j - 1] and s2[j - 1] == s3[i + j - 1]
    return dp[-1][-1]
 
assert is_interleave("ab", "cd", "acbd")
assert not is_interleave("ab", "cd", "adbc")

Both tables use O((n+1)(m+1)) space and cell updates. Distinct-subsequence counts may be large integers, so counting bit operations costs more than treating each addition as constant time.

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. With two nonempty strings this eventually indexes beyond an input boundary, 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 the wrong counts; seeding everything to zero instead yields zero everywhere.

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 wrong recurrence that charges even for a match. It returns max(n, m), because every diagonal now costs 1 and it can pair arbitrary characters; the excess is not generally the number of equal-position matches. Test with two identical strings — the answer must be 0.

Myth: Edit Distance needs three separate tables — one for insertions, one for deletions, one for replacements — because there are three operation types.

Why: The three operations are not three states, they are three transitions into one state. The state is 'how far have I consumed each string', which is fully captured by the pair (i, j). Whatever sequence of edits got you to that pair, the remaining cost is identical — that is the optimal substructure property. Adding a third dimension for operation type multiplies your table size by three and gives you exactly the same answer, because no cell ever needs to know which move produced it.

Steps 1: Because an optimal unit-cost edit solution can be represented as a left-to-right alignment, the state of a partial transformation is fully described by how much of each string has been consumed.

Steps 2: Because that state is a pair of counts (i, j), the number of distinct states is (n+1)(m+1) — finite and polynomial.

Steps 3: Because the remaining minimum cost from a state depends only on that state and not on the path taken to reach it, the problem has optimal substructure and each state can be solved once.

Steps 4: Because the last character of each prefix can only be matched, replaced, deleted, or inserted, each state has at most three predecessors — diagonal, above, left.

Steps 5: Because each of the (n+1)(m+1) states does O(1) work, the total is O(n·m).

Steps 6: Doubling both nonempty lengths quadruples the interior-cell count. Wall-clock ratios also depend on branch behaviour, allocations and the runtime; this is an operation-count argument, not a measured 4x timing guarantee.

Picture: A grid where you start at the top-left corner and must walk to the bottom-right. A diagonal step means you dealt with one character from each string. A step right means you inserted. A step down means you deleted. Every path from corner to corner is one valid edit script, and the cell values are the cheapest path reaching that point.

Trigger: Fires the moment a problem names two strings and asks how they relate — transform, interleave, form, or count subsequences.

Name: Full 2D table

Gain: Direct transcription of the recurrence; you can reconstruct the actual edit script by walking back from the corner; easiest to debug by printing the grid

Cost: O(n·m) table space — about 25 million entries at 5000 × 5000, plus row and integer-object overhead; compare the actual memory budget

Name: Two-row rolling array

Gain: O(min(n, m)) working space when the shorter string indexes columns; the same O(n·m) time order

Cost: The scalar two-row pass alone does not retain a traceback. Divide-and-conquer reconstruction can recover edits with reduced working space. A diagonal stash is needed for a one-row in-place version, not for separate old and new rows.

Use the full table when it makes reasoning or straightforward reconstruction easier. Use rolling rows when the memory budget calls for them. Hirschberg-style divide-and-conquer reconstruction shows that a full table is not a mathematical requirement for producing a witness. Split the source string at its midpoint, compute forward costs to each target-prefix boundary and backward costs from it, and choose a boundary minimising their sum. Recursing on the two resulting rectangles recovers an optimal alignment without retaining the full table; release the temporary rows before descending and account separately for the output edits.

Memory hook — "three neighbours, three edits"

The grid recurrence is easy to recall once you attach each of the three table neighbours to a physical edit. Every interior mismatch cell has three candidate predecessors, all already computed and adjacent; the match branch only needs the diagonal:

• Diagonal dp[i-1][j-1] — replace. Both strings advance one character, so you move diagonally.
• Up dp[i-1][j] — delete from the first string. Only i moved, so you came from directly above.
• Left dp[i][j-1] — insert into the first string. Only j moved, so you came from the left.

The peg: "diagonal replaces, up deletes, left inserts." Picture your finger on a cell and the three cells it can reach behind it — up-left, up, left. There is no fourth neighbour, which is why the mismatch case has exactly three options and not four.

The base-case peg is separate and equally mechanical: "row zero is insertions, column zero is deletions." Converting nothing into j characters costs j inserts; converting i characters into nothing costs i deletes. If you can say those two sentences, you never guess the base cases again.

And the family peg: same grid, different verb. Edit Distance takes a min, LCS takes a max, Distinct Subsequences takes a sum, Interleaving String takes an OR. Draw the grid first, pick the verb second.

What reviewers actually ask

Two-string DP is a favourite because the brute force is exponential, the table is finite, and a reviewer can escalate to space optimisation and reconstruction without changing the problem.

• 72 · Edit Distance (Hard) — Practice selection. Probing whether you can define the state precisely before coding. Follow-up: reduce space to O(min(n, m)), then reconstruct the actual edit script.
• 1143 · Longest Common Subsequence (Medium) — Practice selection. Probing the same grid with a max. Follow-up: 583 · Delete Operation for Two Strings, which is n + m - 2 * LCS.
• 97 · Interleaving String (Medium) — Practice selection. Probing whether you notice that i + j fixes the position in s3, so no third dimension is needed.
• 115 · Distinct Subsequences (Hard) — Practice selection. Probing counting semantics rather than optimisation, and the non-zero base case for the empty target.
• 10 · Regular Expression Matching (Hard) — Practice selection. Probing the same grid with pattern-aware branches, especially the * case that can consume zero or many.
• 44 · Wildcard Matching (Hard) — Practice selection. The simpler sibling of 10; often asked as a warm-up before it.
• 516 · Longest Palindromic Subsequence (Medium) — Practice selection. Probing whether you spot that it is LCS of s against its own reverse.

The escalation almost always runs correct table → space optimisation → reconstruct the answer. Reconstruction is where two-row optimisation bites you, so know that a full grid enables straightforward backtracking; divide-and-conquer reconstruction is an alternative with reduced working memory.

Complexity

Time: O((n+1)(m+1)). For nonempty inputs this is 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+1)(m+1)) for the full table, reducible to O(min(n, m)+1) with rolling rows indexed by the shorter string. The reduction is possible precisely because the recurrence reaches back exactly one row and one column — no cell depends on anything two rows up.

A 1000-by-1000 input fills one million interior cells. This is not a sub-second Python guarantee: measure the implementation and environment if a timing claim matters.

You can now…

• Recognise candidate two-sequence alignment problems, then validate the prefix state against their operations.

• State the subproblem definition as a sentence, and derive the base cases from that sentence rather than by guessing.

• Attach each of the three table neighbours to its edit — diagonal replaces, up deletes, left inserts.

• Write Edit Distance from a blank file with correct dimensions, base cases, and the three-way minimum.

• Derive the distinct legal moves and base cases for LCS (max), Distinct Subsequences (sum), and Interleaving String (OR).

• Roll the grid to two rows indexed by the shorter string; if using one row instead, stash the old diagonal.

• Distinguish full-table backtracking from divide-and-conquer reconstruction; explain why the scalar rolling pass alone does not return an edit script.

Quiz

Self-check (answer follows each question).

Q: In a table declared as (n+1) x (m+1), which characters does dp\[i]\[j] compare?

A: a\[i-1] and b\[j-1]. The index i is a count of consumed characters, not a position, so the last character of the prefix sits one slot earlier.

Q: Why is dp\[i]\[j] = dp\[i-1]\[j-1] when the last characters match, rather than 1 + dp\[i-1]\[j-1]?

A: Matching costs nothing — no edit operation is performed. Any optimal solution can be rearranged so two equal trailing characters are aligned for free, so charging for them would overcount.

Q: For Distinct Subsequences, what is dp\[i]\[0] and why?

A: 1. There is exactly one way to form the empty string from any prefix: choose no characters. Copying Edit Distance's dp\[i]\[0] = i here is the classic wrong answer.

Q: Which three neighbours does a cell read, and what edit does each correspond to?

A: Diagonal dp\[i-1]\[j-1] is replace or match; above dp\[i-1]\[j] is delete from the first string; left dp\[i]\[j-1] is insert from the second string.

Q: What single test case catches a missing equality branch?

A: Two identical strings. The correct answer is 0; a version that always takes the three-way minimum will return the string length instead.

Q: Interleaving String has three strings but only a 2D table. Why is no third dimension needed?

A: Because a valid interleaving consumes exactly i + j characters of s3 by the time it has consumed i of s1 and j of s2. The position in s3 is a function of the other two indices, so it carries no independent information and adding it as a dimension would only duplicate identical states.

Stretch: Remove the equality branch exactly, leaving 1 + min(diagonal, up, left) at every interior cell. For "ab" and "ba" it returns 2, which happens to be correct despite the bug; for "ab" and "ab" it returns 2 instead of 0. A discriminating test matters more than a plausible output.

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.

• Two-sequence prefix problems can use a (n+1) x (m+1) grid; input sizes are a feasibility check, not a proof of the recurrence.

• State the subproblem as an English sentence first; the base cases then follow mechanically instead of being guessed.

• i is a count, not an index — the character you compare is at i-1. That one rule kills most bugs in this family.

• Three moves, three neighbours: diagonal is replace-or-match, above is delete, left is insert.

• The equality branch is free. Test with two identical strings to prove you did not drop it.

• Distinct Subsequences and Interleaving String reuse a prefix grid, but each has its own state, transitions and base cases.

Corrective source notes

• D. S. Hirschberg, A Linear Space Algorithm for Computing Maximal Common Subsequences (1975) — Algorithm C reconstructs a longest common subsequence in linear space; the paper also explicitly describes the minimum-cost edit-distance adaptation. Primary paper read 2026-10-09.

• Introduction to Dynamic Programming - Algorithms for Competitive Programming — Memoization stores subproblem results so repeated states need not be recomputed. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.