Two-String DP · bigonotes

When a problem compares two strings (or arrays), the state is a pair of positions: i in the first and j in the second. At each step you look at the two current characters and either match them or move past one of them. Longest Common Subsequence (LCS) and Edit Distance are the two reference problems; most others are small changes to their transitions.

The idea#

Let solve(i, j) be the answer for the suffixes a[i:] and b[j:] (or the prefixes a[:i], b[:j]; both work). There are two cases.

Characters match: move both pointers. Nothing needs fixing, so this is usually free (or worth +1 in LCS).
Characters differ: try each allowed operation, each of which moves one or both pointers, and take the best.

This is correct because once you've decided what happens to a[i] and b[j], the rest of the problem is the same question on shorter suffixes. There are only len(a) * len(b) such pairs, so the cost is $O(mn)$ .

How to spot it#

Look for these signals in the question.

Two strings or arrays and words such as "common", "transform", "delete to make equal", "interleave", "match a pattern".
Constraints around len ≤ 1000 each, so $O(mn)$ is fine.
A single string compared against itself in reverse is often this pattern too (palindromic subsequence), but it's usually easier as interval DP.

Template#

Here is the top-down shape, written on indices. Each operation from the idea above becomes a different pointer move.

solve(i, j):
    if i == length of a:
        return the cost when a has run out
    if j == length of b:
        return the cost when b has run out
    if a[i] matches b[j]:
        return match value + solve(i + 1, j + 1)
    return best over each allowed operation:
        solve(i + 1, j)           # move past a[i]
        solve(i, j + 1)           # move past b[j]
        solve(i + 1, j + 1)       # move past both
memoize solve on (i, j)
answer: solve(0, 0)

The template uses indices on purpose. Passing slices such as word1[:-1] into the cache works too, but every call copies a string and hashes it. That adds an $O(n)$ factor. Indices make each state $O(1)$ .

Pitfalls#

These mistakes cause the most wrong answers.

Memoizing on string slices instead of indices.
Getting the base cases backwards. Decide what one string running out means for the other: insert the rest, delete the rest, or fail.
Skipping a run of matches in a while loop after the memo lookup, then caching under the advanced indices. It's still correct, but the state you looked up is never stored, so repeated calls redo the work. Prefer one match per call.
When counting, forgetting that a match can also be skipped. Both branches add up.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with LCS and Edit Distance.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Longest Common Subsequence

On a match: 1 + solve(i+1, j+1). On a mismatch: max(solve(i+1, j), solve(i, j+1)). Either string running out gives 0.

Hint: Edit Distance

On a match, move both for free. On a mismatch, take 1 + min of delete (i+1, j), insert (i, j+1) and replace (i+1, j+1). When a runs out, insert the rest of b: len(b) - j. When b runs out, delete the rest of a. Check: horse → ros is 3, intention → execution is 5.

Hint: Delete Operation for Two Strings

On a match: solve(i+1, j+1). On a mismatch: 1 + min(solve(i+1, j), solve(i, j+1)). There is also a one-line shortcut: keep the LCS and delete everything else, so the answer is len(a) + len(b) - 2 * LCS.

Hint: Interleaving String

can(i, j) is true if s1[:i] and s2[:j] can interleave to form s3[:i+j]. The next character of s3 must come from s1[i] or s2[j]. The position in s3 is i + j, so the state needs only i and j.

Hint: Distinct Subsequences

On a match there are two branches, and both add up: use it, solve(i+1, j+1), or skip it, solve(i+1, j). On a mismatch, only skip: solve(i+1, j).

Hint: Regular Expression Matching

The pattern is the second string, and . matches any single character. A * applies to the element before it, so check p[j+1] == '*' before matching p[j]. Then choose: match zero (skip the pair) or consume one text character and stay on the same pattern position.

Hint: Wildcard Matching

? matches any single character. A * gives a choice: match zero characters (skip the star) or consume one character of the text and stay on the star.

Hint: Is Subsequence

Two pointers solve it in one pass. Then think of it as the two-string table: dp[i][j] says whether s[:i] is a subsequence of t[:j], which is the shape the harder problems in this note use.

Key takeaways#

State = one index into each string.
Match: move both. Mismatch: try each operation as a pointer move.
Base cases handle one string running out.
Use indices, not slices, as cache keys.
Many problems reduce to LCS with a formula on top.

Core idea#

To compare two strings, use a pair of positions as the state: i in the first and j in the second. Match the current characters, or move past one of them.

Key points#

Match: move both pointers. It is usually free, or +1 in LCS.
Mismatch: try each allowed operation as a pointer move, and take the best.
Only len(a) * len(b) states exist, so the cost is $O(mn)$ .
Spot it: two strings and "common", "transform", "delete to make equal", "interleave", "match a pattern".
Base cases handle one string running out.
Delete Operation for Two Strings is len(a) + len(b) - 2 * LCS.
Interleaving String needs only (i, j). The position in s3 is i + j.

Transitions#

Problem	On a match	On a mismatch
LCS	`1 + solve(i+1, j+1)`	`max(solve(i+1, j), solve(i, j+1))`
Delete Operation	`solve(i+1, j+1)`	`1 + min(solve(i+1, j), solve(i, j+1))`
Distinct Subsequences	`solve(i+1, j+1) + solve(i+1, j)`	`solve(i+1, j)`
Edit Distance	`solve(i+1, j+1)`	`1 + min(delete, insert, replace)`

In pattern matching, * matches zero characters (skip the star) or one more (consume text, stay on the star). In regex, check p[j+1] == '*' first.

Template#

solve(i, j):
    if i == length of a: return cost when a has run out
    if j == length of b: return cost when b has run out
    if a[i] matches b[j]:
        return match value + solve(i + 1, j + 1)
    return best of solve(i + 1, j), solve(i, j + 1),
                   solve(i + 1, j + 1)     # the allowed moves
memoize solve on (i, j); answer solve(0, 0)

Pitfalls#

Memoizing on string slices. Each call copies and hashes a string. Use indices.
Backwards base cases. When a runs out, insert the rest of b.
Skipping a run of matches in a while loop after the memo lookup. The looked-up state is never stored. Do one match per call.
In Distinct Subsequences, a match can also be skipped. Both branches add up.

Say it in an interview#

"The state is one index into each string."
"On a match both pointers move. On a mismatch each operation is a pointer move."