Two sequences

Any problem comparing two sequences lands on the same table: dp[i][j] is the answer for the first i characters of A and the first j characters of B. Longest common subsequence, edit distance, shortest common supersequence, string interleaving — one grid, n x m states, a different recurrence in each cell.

Recognising that is most of the work. The rest is deciding what happens to the last character of each prefix.

The last-character decision

Standing at cell (i, j), look only at A[i-1] and B[j-1], the last characters of the two prefixes. There are three moves and no others:

• They match, so pair them off and the remaining problem is (i-1, j-1).
• Drop the last character of A, leaving (i-1, j).
• Drop the last character of B, leaving (i, j-1).

Every two-sequence recurrence is a choice among those three cells. The problem only decides which are legal and whether you take a max, a min or a sum.

The longest-common-subsequence table for ABC against ACB, with the three neighbours a cell reads100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

The same table, two recurrences

Longest common subsequence maximises pairings:

def lcs(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    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] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

Edit distance minimises operations, over exactly the same three neighbours:

def edit(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = i                       # delete every character of A
    for j in range(m + 1):
        dp[0][j] = j                       # insert every character of B
    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]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1],   # replace
                                   dp[i - 1][j],       # delete from A
                                   dp[i][j - 1])       # insert into A
    return dp[n][m]

Side by side the family shows itself:

	Longest common subsequence	Edit distance
Base row and column	0	i and j
Characters match	dp[i-1][j-1] + 1	dp[i-1][j-1], free
They do not	max of the two drops	1 + min of all three
Direction	maximise	minimise

The base cases carry the difference in meaning. An empty prefix shares nothing with anything, so LCS starts at 0; turning an i-character string into an empty one costs i deletions, so edit distance starts at i. Leaving the LCS base of 0 in an edit-distance table is the standard bug, and it never raises: the zero row says an empty prefix is free to reach, so every cell comes out at most its true value and the function under-reports rather than over-reports. The fastest tell is an empty argument — edit('', 'abc') returns 0 instead of 3. Across 20,000 random pairs from a three-letter alphabet with lengths 0 to 6, the zero-base version was too low on 84% of them and too high on none, which is why a sample that happens to pass tells you nothing.

Cost is the product from what DP actually is: n x m states, constant work each, so O(n x m) time. At n = m = 5,000 that is 25 million cells — a quarter of a second at the 10^8 simple operations per second used in complexity by counting, and several seconds in Python, which is why this shape usually comes with n at most a few thousand.

Rolling the rows

Row i reads row i-1 and cells to its left in row i. Nothing ever reads row i-2, so only two rows need to exist:

def lcs_rolled(a, b):
    if len(b) > len(a):
        a, b = b, a                        # keep the shorter string on the columns
    prev = [0] * (len(b) + 1)
    for x in a:
        cur = [0] * (len(b) + 1)
        for j, y in enumerate(b, 1):
            cur[j] = prev[j - 1] + 1 if x == y else max(prev[j], cur[j - 1])
        prev = cur
    return prev[len(b)]

Swapping so that B is the shorter string makes the space O(min(n, m)). At n = m = 5,000 the full table is 25 million cells — about 200 MB at 8 bytes each, and considerably more in CPython, where every cell is a boxed object — while two rows are 5,001 cells each, roughly 80 KB. That is a factor of 2,500.

What you lose is the walk back. Reconstructing the actual subsequence means starting at dp[n][m] and stepping to whichever neighbour produced it, which needs the whole table. Keep the full grid when the answer is the sequence, roll it when the answer is a number. The same trade-off appears one dimension down in linear DP and again in the knapsack family, where the rolling is over items rather than rows.

Reconstruction, when you need it

Walk backwards from (n, m) and reverse the moves you made:

def lcs_string(a, b, dp):
    i, j, out = len(a), len(b), []
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1])
            i, j = i - 1, j - 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(out))

The walk is O(n + m) and touches one cell per step, so reconstruction is free next to the fill. Ties break arbitrarily: several subsequences usually share the same length, and any of them is a correct answer.

In an interview

Draw a 4 by 4 grid with both strings on the axes and fill six cells by hand before writing code. It takes ninety seconds, catches a wrong base row immediately, and gives you something to point at while you explain the transition.

Say the state in one sentence with both indices meaning the same thing on each axis — "dp[i][j] is the answer for the first i of A and the first j of B" — and be consistent about whether i counts characters or indexes them. Mixing the two conventions halfway through the table is the most common source of an off-by-one here.

Offer the space reduction as a follow-up rather than writing it first — the full table is easier to debug, and the rolled version is a two-line change you can describe: "keep only the previous row, put the shorter string on the columns, O(min(n, m)) space, and I give up reconstruction."

The mistake that loses points: deriving the recurrence from an example instead of from the decision. A candidate who reads the pattern off a filled table cannot say why the mismatch branch takes a max of two cells and not three, and gets stuck the moment the problem changes to a variant.

Check yourself

Why does the mismatch branch of LCS never look at dp[i-1][j-1], while edit distance does?

Because with a mismatch, dropping both last characters is never better than dropping one: dp[i-1][j-1] is at most both dp[i-1][j] and dp[i][j-1], so the max already covers it. Edit distance needs the diagonal because replacing one character with another is a real operation with a real cost of 1.

A and B are both 5,000 characters. Estimate time and memory for the full table, and for the rolled version.

5,000 x 5,000 = 25 million states with constant work each — a quarter of a second at 10^8 operations per second, and around 200 MB at 8 bytes a cell. Two rows are 10,002 cells, roughly 80 KB: same time, memory down by three orders of magnitude.

You rolled the table to two rows and now the interviewer asks for the actual subsequence. What do you say?

That reconstruction needs the full grid, because the walk back reads cells from every row. Either restore the O(n x m) table, or store one back-pointer per cell, which costs the same memory. Hirschberg's divide-and-conquer variant recovers the sequence in O(min(n, m)) space at twice the time, which is the answer if they push.