Longest Common Subsequence

Hints

1. What's the state? Define f(i, j) = length of LCS of a[0..i) and b[0..j) (prefixes of length i and j). The answer is f(n, m).
2. Base case. If either prefix is empty, LCS is 0. So f(0, j) = 0 for all j, and f(i, 0) = 0 for all i.
3. Transition. If a[i-1] == b[j-1], the matching character can extend the LCS of the two shorter prefixes: f(i, j) = f(i-1, j-1) + 1. If they don't match, the LCS ignores at least one of the two characters: f(i, j) = max(f(i-1, j), f(i, j-1)).
4. Why the index shift. a[i-1] is the i-th character (1-indexed), we use 1-indexed table positions and 0-indexed string positions. The +1 table padding is what gives us a clean base case at f(0, *) and f(*, 0).
5. Tabulation order. Build the table row by row (or column by column). Each cell depends only on cells above and to the left, both already computed.
6. Space optimisation. The transition uses only the previous row and the current row's left neighbour. Two 1D arrays (or one with careful in-place updates) suffice. Reduces space from O(n × m) to O(min(n, m)).

Solution, three approaches

Approach 1 · Memoised recursion. O(n × m) time, O(n × m) space

from functools import cache

def lcs_memo(a, b):
    @cache
    def f(i, j):
        if i == 0 or j == 0: return 0
        if a[i-1] == b[j-1]:
            return f(i-1, j-1) + 1
        return max(f(i-1, j), f(i, j-1))
    return f(len(a), len(b))

Reads directly off the recurrence. The cache decorator memoises every (i, j) pair, ensuring each is computed at most once. Stack depth is O(n + m) which is fine for the constraint range; for larger inputs, prefer tabulation.

Approach 2 · Tabulation. O(n × m) time, O(n × m) space

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]

Fills the table left-to-right, top-to-bottom. The boundary row and column are zeros, the empty-prefix case. Each cell does O(1) work; the table has (n+1) × (m+1) cells; total O(n × m).

This is the version to write in production. The recursion-overhead difference vs Approach 1 is small but real.

Approach 3 · Space-optimised tabulation. O(n × m) time, O(min(n, m)) space

The transition for row i depends only on row i and row i−1. We don't need the full table, just the previous row. Two 1D arrays of length min(n, m) + 1:

def lcs_space(a, b):
    if len(a) < len(b): a, b = b, a                  # iterate the shorter string in the inner loop
    n, m = len(a), len(b)
    prev = [0] * (m + 1)
    curr = [0] * (m + 1)
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i-1] == b[j-1]:
                curr[j] = prev[j-1] + 1
            else:
                curr[j] = max(prev[j], curr[j-1])
        prev, curr = curr, prev                       # swap; reuse curr as next row's prev
        for j in range(m + 1): curr[j] = 0            # clear for next iteration
    return prev[m]

The swap-and-clear pattern avoids allocating fresh arrays each iteration. The inner loop iterates the shorter string, that's why we swap at the top.

An even tighter version uses a single 1D array with a temporary variable to track the "previous row's diagonal" value. Slightly faster on cache; harder to read. For interviews, the two-array version is the right balance.

Reconstructing the actual subsequence

The DP returns the length. To return the actual subsequence, walk the table backward from dp[n][m]: at each cell, decide whether the answer included the matching character (when a[i-1] == b[j-1]) or came from above or left.

def lcs_string(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):
            dp[i][j] = (dp[i-1][j-1] + 1) if a[i-1] == b[j-1] else max(dp[i-1][j], dp[i][j-1])
    out = []
    i, j = n, m
    while i > 0 and j > 0:
        if a[i-1] == b[j-1]:
            out.append(a[i-1])
            i -= 1; j -= 1
        elif dp[i-1][j] >= dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(out))

Reconstruction takes O(n + m), the backward walk visits at most one cell per row or column.

Complexity comparison

Edge cases to verify

• Identical strings: the diagonal of the DP table accumulates 1 per step; answer = length.
• Completely disjoint alphabets: answer = 0; every transition takes the max-of-neighbours branch.
• One string empty: the constraint says length ≥ 1, but the boundary handling makes 0-length correct anyway.
• Repeated characters: the DP handles them correctly; no special case needed.
• Very long strings (n × m > memory): the space-optimised version handles n = m = 10⁴ comfortably; pure tabulation would need 400 MB for n = m = 10⁴ ints.

Where beginners go wrong

• Confusing subsequence with substring. Substrings are contiguous; subsequences are not. "Longest common substring" is a different problem (the recurrence resets to 0 on mismatch instead of taking the max).
• Index off-by-one between table and string. The table is 1-indexed (size n+1 × m+1); the string is 0-indexed. a[i-1] is the i-th character. Mixing them is the most common bug here.
• Missing the boundary zeros. Without the dummy row and column of zeros, the recurrence at i=1 or j=1 fails, there's no dp[0][j-1] to read from. The +1 padding is the price for clean code.
• Greedy with two pointers. "Match each character of a in b" doesn't work, it gives a long common subsequence but not necessarily the longest. The DP is required.
• Returning dp instead of dp[n][m]. The DP value at the final cell is the answer; the entire table is not.

Interview follow-ups to expect

• "Return the subsequence itself, not the length." Use the backward-walk reconstruction (Approach above).
• "Edit distance, minimum number of insertions/deletions/substitutions to transform A into B." A close cousin of LCS. The DP recurrence has three branches (the three edit operations). Same shape; different transition.
• "Shortest common supersequence, shortest string containing both A and B as subsequences." Length is n + m − LCS(A, B). Reconstruction walks the LCS table similarly.
• "How would you parallelise this DP?" Anti-diagonals can be computed in parallel, each cell on a given anti-diagonal depends only on cells in earlier anti-diagonals. Cache-aware implementations partition the table this way.
• "What if the alphabet is large (say, words instead of characters)?" The DP doesn't care about the alphabet, only about character equality. The hash comparison is O(L) per check for long-string tokens, which becomes the bottleneck.

Related reading

• State Design Templates, the broader DP framework; LCS is shape 3 (2D string).
• Dynamic Programming, the module that frames LCS in context.
• Knapsack Variants, a different 2D DP shape for comparison.