DP problems — edit distance (Levenshtein): Question bank

Before you start, keep the three arrows from the parent in your head:

↖ diagonal = compare the current characters (free if equal, $+ 1$ if substituting),
↑ up = delete a character of $A$ ,
← left = insert a character of $B$ .

Everything below is a stress-test of that picture.

True or false — justify

The min-of-three rule always applies, even when characters match.

False. On a match you take the pure diagonal

d p [i - 1] [j - 1]

with no $+ 1$ ; forcing the min-of-three would let a stray

+ 1

path win and over-count the distance.

Edit distance equals the difference in string lengths.

False. Length difference is only a lower bound: you cannot fix a length gap of

k

with fewer than

k

insert/delete moves, but substitutions add cost even when lengths are equal (e.g. "cat" → "dog" is 3, not 0).

Edit distance is symmetric:

d (A, B) = d (B, A)

True. Every insert into

A

is a delete from

B

and vice-versa, and substitution is its own inverse — so any optimal edit script reverses at the same cost.

If two strings are equal, their edit distance is 0.

True. Every character matches, so the diagonal carries 0 all the way to

d p [m] [n]

; no operation is ever forced.

d p [i] [j]

compares characters A[i] and B[j].

False.

d p [i] [j]

covers the first $i$ and first $j$ characters, so the current characters are the 0-indexed A[i-1] and B[j-1]. This off-by-one is the single most common bug.

The order in which you fill the table doesn't matter.

False. A cell reads its up, left, and up-left neighbours, so those must already be filled — row-by-row (or column-by-column) top-left to bottom-right is required.

Edit distance obeys the triangle inequality:

d (A, C) \leq d (A, B) + d (B, C)

True. You can always convert

A \to B

then

B \to C

; that combined script costs the sum, so the optimal

A \to C

cost is no larger. It makes Levenshtein a genuine metric.

The empty string has a well-defined edit distance to any string.

True.

d ("", B) = ∣ B ∣

(insert every char) and

d (A, "") = ∣ A ∣

(delete every char) — these are exactly the base row and column.

Allowing substitutions can never make the answer larger than an insert+delete-only model.

True. A substitution costs 1 but replaces a delete-then-insert pair that would cost 2, so having it available only ever lowers (or ties) the total.

Spot the error

"For A[i-1] != B[j-1], I wrote dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) (no +1)."

Error: the

+ 1

is missing. A mismatch forces one edit, so it must be

1 + min (\dots)

; without it the table stays flat and reports distances that are impossibly small.

"I initialised the whole table to 0, then ran the double loop."

Error: row 0 must be

d p [0] [j] = j

and column 0 must be

d p [i] [0] = i

, not 0. Leaving them at 0 lets the recurrence read false "free" prefixes and undercount.

"On a match I did dp[i][j] = 1 + dp[i-1][j-1]."

Error: a match costs nothing for that position; it should be dp[i][j] = dp[i-1][j-1] with no

+ 1

. Adding 1 inflates every aligned character.

"Delete comes from the left cell dp[i][j-1]."

Error: delete-from-

A

comes from above,

d p [i - 1] [j]

(shorter

A

, same

B

). The left cell

d p [i] [j - 1]

is the insert move.

"I used only two neighbours (up and left) because substitution is just delete + insert."

Error: dropping the diagonal loses the cheap 1-cost substitution and the free match; you'd compute a different distance (the insert/delete-only variant), which can be strictly larger.

"To save space I kept only the previous column but iterated row by row."

Error: if you sweep row by row you need the previous row (and a running left value). Keeping a column while iterating by rows reads stale data — the kept array must match the sweep direction.

Why questions

Why does the recurrence only ever inspect the last character of each prefix?

Any edit script that fixes A[0..i) into B[0..j) must do exactly one thing about the final position; fixing it peels off one character and leaves a strictly smaller edit-distance problem you already solved — that's Optimal Substructure.

Why is DP faster than plain recursion here?

The naive recursion recomputes the same prefix pairs exponentially often; those are Overlapping Subproblems, so caching each

d p [i] [j]

once turns exponential time into

O (mn)

— see Recursion and Memoization.

Why do long common subsequences make the distance small?

Every character that matches passes down the diagonal for free, so the only cost comes from positions outside a shared alignment — which is why edit distance is intimately tied to the Longest Common Subsequence.

Why can we reduce space to

O (min (m, n))

A cell reads only row

i - 1

and column

j - 1

, so we never need older rows; keeping one previous row (choosing the shorter string as the row dimension) suffices — this is Space Optimization in DP.

Why do we take the minimum over the candidate moves rather than the sum?

Each candidate is a different complete strategy for the last move, and we want the single cheapest one — we choose one path, we don't perform all of them, so it's a min, not a sum.

Why is

d p [m] [n]

(bottom-right) the final answer and not

d p [0] [0]

d p [i] [j]

grows with prefix length;

d p [m] [n]

uses the full strings, whereas

d p [0] [0] = 0

is just the trivial "two empty strings" seed the table starts from.

Edge cases

What is

d (A, B)

when

A

is empty?

It is

∣ B ∣

: you must insert every character of

B

, and nothing cheaper exists — this is exactly the base row

d p [0] [j] = j

What is

d (A, B)

when both strings are empty?

0. Two empty strings need no edits, giving the corner seed

d p [0] [0] = 0

What is the edit distance between two identical strings of length

n

0, regardless of

n

: every character matches so the diagonal carries 0 through to

d p [n] [n]

What is the maximum possible edit distance between strings of length

m

and

n

max (m, n)

: in the worst case you substitute the overlapping

min (m, n)

positions and insert/delete the remaining

∣ m - n ∣

, and you never need more than

max (m, n)

moves.

What is the distance between two strings of the same length that share no characters at any position?

Exactly their common length: every position mismatches and can be fixed by one substitution each, and no insert/delete could beat that since lengths already agree.

B

is a prefix of

A

(e.g. "apple" → "app"), what is the distance?

The length gap

∣ A ∣ - ∣ B ∣

: all shared characters align for free and you only delete the trailing extras of

A

B

A

with one extra character inserted somewhere, what is the distance?

1 — a single insertion suffices, and the length difference forces at least 1, so it's exactly 1.

What happens to the answer if you swap which string is the rows and which is the columns?

Nothing — the distance is symmetric, so the table transposes but

d p [m] [n]

is unchanged; only the delete/insert labels on the arrows swap roles.

Connections

Parent — the recurrence, base cases, and worked tables these traps stress-test.
Dynamic Programming, Optimal Substructure, Overlapping Subproblems — the machinery behind "why a recurrence exists."
Recursion and Memoization, Space Optimization in DP — implementation trade-offs probed above.
Longest Common Subsequence, Sequence Alignment — where "shared subsequences are free" leads next.