Two-string DP

Problem

You are given two strings, a and b, and asked something that depends on how they line up: the longest piece they share in order, the fewest edits to turn one into the other, whether the second can be woven from the first and a third, how many times one hides inside the other, or whether a pattern with wildcards matches a text. Trying every alignment is exponential. But any alignment ends by looking at the last letter of each prefix, and what remains is the same question about shorter prefixes. There are only (|a| + 1) × (|b| + 1) such pairs of prefixes, and each is solved once.

Intuition

Stand at the ends of two prefixes and look at the last letter of each. If they are equal, they can be paired, and then the rest of the problem is what is left of both prefixes with that pair removed. If they differ, something has to give: in common subsequence, one of the two letters is not used; in edit distance, one of three edits repairs the mismatch. Either way the leftover problem is a pair of shorter prefixes, so the answer for (i, j) is built from its neighbours (i - 1, j), (i, j - 1) and (i - 1, j - 1).

Draw a grid with the letters of a down the side and the letters of b across the top, plus an empty prefix first on each axis. Row 0 and column 0 are the base cases, where one prefix is empty and the answer is immediate. Everything else is filled left to right and top to bottom, so each cell finds its three neighbours already written. The answer is the bottom-right cell.

The three neighbours have meanings: above (i - 1, j) means "use up a letter of a only", left means "use up a letter of b only", and the diagonal means "use up one of each". Reading the table backwards from the corner, choosing the neighbour that explains each value, recovers the actual alignment, not just its score.

Rows are prefixes of the first word, columns prefixes of the second; the grey row and column are the empty prefix. Blue cells trace the walk back from the corner that recovers one longest common subsequence. The diagram scrolls sideways on a narrow screen.

Mechanics

Longest common subsequence

Let lcs[i][j] be the length of the longest common subsequence of a[:i] and b[:j]. The base case is 0 whenever i or j is 0. If a[i-1] == b[j-1], then lcs[i][j] = lcs[i-1][j-1] + 1; otherwise lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]).

Why is matching the last letters always safe? Take any longest common subsequence of the two prefixes. If it does not use both final letters, swapping its last pair for those final letters keeps it valid and the same length, so some optimal answer uses them. When the letters differ, an answer cannot use both of them, so it ignores at least one, which is exactly the two cases in the max.

Edit distance

Let d[i][j] be the fewest insertions, deletions and replacements that turn a[:i] into b[:j]. Turning a prefix into the empty string costs its length, so d[i][0] = i and d[0][j] = j. Otherwise, if the last letters are equal, nothing needs fixing there and d[i][j] = d[i-1][j-1]; if not, d[i][j] = 1 + min(d[i-1][j], d[i][j-1], d[i-1][j-1]), where the three options are delete the letter from a, insert the letter of b, and replace one with the other.

The first row and column count up because an empty prefix needs one insertion or deletion per letter. Blue cells are the walk back from the corner; each step up, left or diagonal is one delete, one insert or one replace (or a free diagonal match).

Counting subsequences

Let ways[i][j] be the number of ways t[:j] appears as a subsequence of s[:i]. The empty target appears exactly once in any prefix, so ways[i][0] = 1, and a non-empty target never appears in an empty source, so ways[0][j] = 0. Then ways[i][j] = ways[i-1][j] (skip the source letter) plus, when s[i-1] == t[j-1], ways[i-1][j-1] (use it for the last target letter). The two cases split the ways by whether the last source letter is used, so nothing is counted twice.

Interleaving

Let ok[i][j] say that the first i letters of x and the first j of y, each in order, can weave into the first i + j letters of the target. Cell (i, j) is true if (i - 1, j) is true and x[i-1] equals target letter i + j - 1, or if (i, j - 1) is true and y[j-1] equals that same letter. The length check len(x) + len(y) == len(target) goes first.

Wildcard matching

Let m[i][j] say that text[:i] matches pattern[:j], where . matches any one letter and x* matches zero or more copies of x. For an ordinary pattern letter, the cell is true when the letters match and m[i-1][j-1] is true. When the pattern letter is a star (which belongs to the token before it), the cell is true if the token is skipped, m[i][j-2], or if it consumes one more text letter that it matches, m[i-1][j]. An empty text can still match patterns like a*, so row 0 needs filling too, not just the corner.

Worked example

Common subsequence. For "plumber" and "humbler" the last row of the table is 0, 0, 1, 2, 3, 3, 4, 5, so the longest common subsequence has length 5. Walking back from the corner while matching letters recovers "umber".

Edit distance. Turning "flaw" into "lawn" takes 2 edits: delete f, then insert n. The table's last row is 4, 3, 2, 1, 2.

Counting. The word "ab" appears 5 times as a subsequence of "aabab". The last column of the count table is 0, 0, 0, 2, 2, 5 as the source grows letter by letter: each b adds one way for every earlier a that is still waiting for it.

Interleaving. The words "ab" and "cd" can be woven into "acbd" (yes) but not "adbc" (no), because "d" would have to come before "c", which reverses their order in the second word.

Wildcards. The pattern "ab*c" matches the text "abbc": the star lets the b repeat twice. The pattern "a.*d" does not match it, because the text has no final d.

Implementation

def longest_common_subsequence(a, b):
    previous = [0] * (len(b) + 1)
    for x in a:
        current = [0]
        for j, y in enumerate(b, 1):
            current.append(previous[j - 1] + 1 if x == y else max(previous[j], current[j - 1]))
        previous = current
    return previous[-1]


def min_distance(a, b):
    previous = list(range(len(b) + 1))
    for i, x in enumerate(a, 1):
        current = [i]
        for j, y in enumerate(b, 1):
            if x == y:
                current.append(previous[j - 1])
            else:
                current.append(1 + min(previous[j], current[j - 1], previous[j - 1]))
        previous = current
    return previous[-1]

Variations and edge cases

def num_distinct(source, target):
    ways = [1] + [0] * len(target)
    for x in source:
        for j in range(len(target), 0, -1):        # right to left so each source letter is used once
            if x == target[j - 1]:
                ways[j] += ways[j - 1]
    return ways[-1]


def is_interleave(x, y, target):
    if len(x) + len(y) != len(target):
        return False
    ok = [True] + [False] * len(y)
    for j in range(1, len(y) + 1):
        ok[j] = ok[j - 1] and y[j - 1] == target[j - 1]
    for i in range(1, len(x) + 1):
        ok[0] = ok[0] and x[i - 1] == target[i - 1]
        for j in range(1, len(y) + 1):
            k = i + j - 1
            ok[j] = (ok[j] and x[i - 1] == target[k]) or (ok[j - 1] and y[j - 1] == target[k])
    return ok[-1]


def is_match(text, pattern):
    m = [[False] * (len(pattern) + 1) for _ in range(len(text) + 1)]
    m[0][0] = True
    for j in range(2, len(pattern) + 1):
        if pattern[j - 1] == "*":
            m[0][j] = m[0][j - 2]
    for i in range(1, len(text) + 1):
        for j in range(1, len(pattern) + 1):
            if pattern[j - 1] == "*":
                m[i][j] = m[i][j - 2] or (pattern[j - 2] in (text[i - 1], ".") and m[i - 1][j])
            else:
                m[i][j] = pattern[j - 1] in (text[i - 1], ".") and m[i - 1][j - 1]
    return m[-1][-1]

• Off-by-one between the table and the strings. Table index i means "the first i letters", so the letter being added is a[i - 1]. Mixing the two is the most common bug.
• Empty strings. The table has a row and column for the empty prefix, so empty inputs work without a special case. The edit distance to an empty string is the other string's length.
• Rolling arrays. One row is enough, since row i needs only row i - 1. When you shrink to a single list, the diagonal value is overwritten before use unless you iterate right to left (counting) or save it.
• Reconstruction needs the full table. If the question asks for the actual subsequence or edit script, keep all rows; with only the length, keep two.
• Star handling. A * never stands alone: it modifies the token before it, so look at pattern[j - 2]. Rows for an empty text must also be filled, or patterns like a*b* fail on the empty string.
• Counting overflow. The counts can be huge; Python integers do not overflow, but some problems ask for the answer modulo a number.

Complexity and tradeoffs

• Time: O(m · n) for strings of lengths m and n; each cell does constant work. The wildcard table is O(|text| · |pattern|).
• Space: O(m · n) with the full table, O(min(m, n)) when only the final value is needed and you keep one or two rows.
• Baseline. Comparing every subsequence pair is exponential; the naive recursion without a cache is O(2^{m + n}) in the worst case.
• Bit tricks. For tiny alphabets, longest common subsequence can run word-parallel in about O(m · n / 64), but that is rarely wanted in interviews.
• When it fails. Three or more strings multiply the dimensions; with k strings the table has n^k cells. Questions on a single string with ranges, like bursting balloons, use other state shapes instead.

Problems

Longest Common Subsequence is the cleanest place to learn the table and Edit Distance adds the three-way choice. Interleaving String, Distinct Subsequences and Regular Expression Matching change the cell's meaning but keep the same grid.

Medium

• 72. Edit Distance NeetCode 150 NeetCode 250
  A cell holds the cost to turn one prefix into another, and its three neighbours correspond to an insert, a delete and a replace.
• 97. Interleaving String NeetCode 150 NeetCode 250
  A cell says whether the first i and j characters can form the first i+j of the target, coming from above or from the left.
• 1143. Longest Common Subsequence Blind 75 NeetCode 150 NeetCode 250
  Matching last characters extend the common subsequence of both shorter prefixes, and otherwise drop a character from either string.

Hard

• 10. Regular Expression Matching NeetCode 150 NeetCode 250
  Let a cell mean whether a prefix of the text matches a prefix of the pattern, and treat a star as either zero copies or one more copy of the previous token.
• 115. Distinct Subsequences NeetCode 150 NeetCode 250
  Count the ways a prefix of the target appears in a prefix of the source: a match may be used or skipped, a mismatch can only be skipped.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 32. Longest Valid Parentheses Hard

Connections

This is the two-dimensional cousin of the one-sequence tables on the linear DP page, and it uses the same grid-filling order as grid DP. The recurrences for edit distance and common subsequence are the textbook examples behind sequence alignment in biology and the diff tool.

Check yourself

References

• Wagner, R. and Fischer, M., "The string-to-string correction problem", Journal of the ACM 21(1), 1974.
• Needleman, S. and Wunsch, C., "A general method applicable to the search for similarities in the amino acid sequence of two proteins", Journal of Molecular Biology 48, 1970.
• Hirschberg, D. S., "A linear space algorithm for computing maximal common subsequences", Communications of the ACM 18(6), 1975.
• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, chapter 14, longest common subsequence.
• Skiena, S., The Algorithm Design Manual, chapter 10, approximate string matching.
• Sedgewick and Wayne, Algorithms, section 4.4 (acyclic shortest paths), since an edit-distance table is a shortest path through an alignment grid, and section 6.3 (suffix arrays) for longest common substring, the contiguous cousin of LCS.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.