Longest Common Subsequence

Longest Common Subsequence is the parent of the two-string DP family. Once you can fill its table, Edit Distance, shortest common supersequence and "minimum deletions to make two strings equal" are all small changes.

The state is a pair of prefixes, and every cell asks one question: do the last letters of the two prefixes match?

The problem

Given two strings, return the length of their longest common subsequence — the longest string you can get from both by deleting some letters (possibly none) without changing the order of the rest. It does not have to be contiguous.

• "plane" and "apple" → 3. "ple" appears in both: p-l-e in plane, p-l-e in apple.
• "abc" and "xyz" → 0. No letter in common.

Constraints: 1 ≤ lengths ≤ 1,000, lowercase English letters.

Clarifying questions

• Subsequence or substring? Subsequence — gaps are allowed. (Longest common substring is a different table; see the follow-ups.)
• Length or the string? Length. Recovering the string is shown below.
• Case-sensitive? Yes, but the input is lowercase.

Approach 1: the simple way — recurse on the first letters

Compare the first letters of the two strings. If they match, that letter can start the common subsequence: take it, and continue with both strings shortened. If not, one of the two letters is not used — try dropping each and keep the better.

1def lcs_rec(a: str, b: str) -> int:2    """best(i, j) = LCS length of a[i:] and b[j:]."""3    def best(i: int, j: int) -> int:4        if i == len(a) or j == len(b):5            return 0                                     # one string is used up6        if a[i] == b[j]:7            return 1 + best(i + 1, j + 1)                # take the matching letter8        return max(best(i + 1, j), best(i, j + 1))       # drop one letter or the other9    return best(0, 0)

Why it is too slow. When letters do not match, each call makes two more, and the strings shrink by only one letter per call. Two 12-letter strings with nothing in common take 5,408,311 calls; at 14 letters, 80,233,199. At 1,000 letters it never finishes. Yet there are only (m + 1) × (n + 1) different (i, j) pairs, so the tree is full of repeats.

The key insight

The LCS of two prefixes depends only on their last letters:

• They match → that letter ends the common subsequence. dp[i][j] = dp[i − 1][j − 1] + 1.
• They differ → at least one of the two is not in the answer. Drop the last letter of the first string, or of the second, and keep the better: dp[i][j] = max(dp[i − 1][j], dp[i][j − 1]).

The state is dp[i][j] = the LCS length of the first i letters of a and the first j letters of b. Row 0 and column 0 are 0: an empty string shares nothing.

Why is taking a match always safe? If a[i − 1] == b[j − 1] and some best answer did not use them together, you could swap its last letter for this matching pair and lose nothing. So the diagonal move never costs you.

Approach 2: memoisation

1from functools import cache23def lcs_memo(a: str, b: str) -> int:4    @cache5    def best(i: int, j: int) -> int:6        if i == len(a) or j == len(b):7            return 08        if a[i] == b[j]:9            return 1 + best(i + 1, j + 1)10        return max(best(i + 1, j), best(i, j + 1))11    return best(0, 0)

O(m × n) states, O(1) work each: O(m × n) time and space. The stack can reach m + n deep — 2,000 for the largest inputs, past Python's default limit.

Approach 3: tabulation

1def lcs_table(a: str, b: str) -> int:2    """dp[i][j] = LCS length of a[:i] and b[:j]."""3    m, n = len(a), len(b)4    dp = [[0] * (n + 1) for _ in range(m + 1)]    # row 0 and column 0 stay 05    for i in range(1, m + 1):6        for j in range(1, n + 1):7            if a[i - 1] == b[j - 1]:8                dp[i][j] = dp[i - 1][j - 1] + 1   # extend the diagonal9            else:10                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])11    return dp[m][n]

Dry run for a = "plane" (rows) and b = "apple" (columns):

        ""  a  p  p  l  e   ""    0  0  0  0  0  0   p     0  0  1  1  1  1   l     0  0  1  1  2  2   a     0  1  1  1  2  2   n     0  1  1  1  2  2   e     0  1  1  1  2  3

Read a few cells. Row p, column p (first p): a match, so 1 + the diagonal 0 = 1. Row l, column l: a match, so 1 + the diagonal (p, second p) = 1 + 1 = 2. Row a, column a: a match, 1 + 0 = 1 — a different, shorter subsequence. Row e, column e: a match, 1 + the diagonal (n, l) = 1 + 2 = 3. The answer sits in the bottom-right corner: 3.

Recovering the string. Start at the corner. If the two letters match, that letter is in the answer — step diagonally. Otherwise step to whichever neighbour (up or left) holds the larger value. For this table the walk collects e, l, p, which reversed is "ple".

Approach 4: two rows

Row i reads only row i − 1, so keep two rows. Put the shorter string along the row for O(min(m, n)) space.

1def lcs(a: str, b: str) -> int:2    """LCS length with two rows of memory."""3    if len(b) > len(a):4        a, b = b, a                              # keep the row short5    prev = [0] * (len(b) + 1)6    for i in range(1, len(a) + 1):7        cur = [0] * (len(b) + 1)8        for j in range(1, len(b) + 1):9            if a[i - 1] == b[j - 1]:10                cur[j] = prev[j - 1] + 1         # diagonal: previous row, previous column11            else:12                cur[j] = max(prev[j], cur[j - 1])13        prev = cur14    return prev[-1]

Two rows are needed, not one, because a match reads the old value at j − 1, which a single row would already have overwritten. (One row plus a saved "diagonal" variable also works.) Complexity: O(m × n) time, O(min(m, n)) space. The price: you can no longer walk back to recover the string.

Edge cases

• No common letters — every cell takes the max of zeros; the answer is 0.
• Identical strings — the diagonal fills 1, 2, 3, …; the answer is the length.
• One string empty — excluded by the constraints, but the code returns 0 anyway.
• Repeated letters — "aaa" and "aa" give 2; the table never uses one letter twice because every match moves diagonally.

Follow-ups

• Fewest deletions to make the two strings equal — delete everything outside the LCS: m + n − 2 × LCS.
• Shortest string containing both as subsequences — m + n − LCS: the shared letters are written once.
• Longest common substring (contiguous) — on a match dp[i][j] = dp[i − 1][j − 1] + 1, on a mismatch 0, and the answer is the largest cell anywhere, not the corner.
• Longest palindromic subsequence — the LCS of a string and its reverse.