Longest Common Subsequence (LeetCode 1143)

The problem

Given two strings a and b, return the length of their longest common subsequence: the longest sequence of characters that appears in both, in the same order, though not necessarily next to each other. Return 0 if they share nothing.

Input:  a = "abcde", b = "ace"
Output: 3

"ace" appears in both strings in order (in "abcde" as positions 0, 2 and 4).

How to think about it

Start with brute force. List every subsequence of a (2ᵐ of them) and check each against b. That is O(2ᵐ · n), hopeless for strings of length 1,000.

The key insight: compare the last characters. Let dp[i][j] be the LCS length of the prefixes a[:i] and b[:j]. Look at a[i-1] and b[j-1]:

• If they match, that character can end the common subsequence, so dp[i][j] = dp[i-1][j-1] + 1 (the diagonal plus one).
• If they don’t match, at least one of them is not in the LCS. Drop one or the other and take the better: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Base cases are free. An empty prefix shares nothing, so row 0 and column 0 are all 0. Padding the table by one row and column means you never index out of range.

Which pattern is this? 2-D DP over two sequences. The tell is “compare two strings or arrays and find the best alignment”: the state is a pair of prefix lengths, and each cell depends on its top, left and top-left neighbours. Edit Distance and many others follow this exact template.

Approach

1. Build a (len(a) + 1) × (len(b) + 1) table of zeros.
2. For each i from 1 to len(a) and j from 1 to len(b):
   • If a[i-1] == b[j-1], set dp[i][j] = dp[i-1][j-1] + 1.
   • Otherwise set dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
3. Return the bottom-right cell.

Solution

def lcs(a, b):
    dp = [[0] * (len(b)+1) for _ in range(len(a)+1)]   # dp[i][j] = LCS of a[:i], b[:j]
    for i in range(1, len(a)+1):
        for j in range(1, len(b)+1):
            if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] + 1      # match: extend diagonal
            else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])           # drop one character
    return dp[-1][-1]
# lcs("abcde", "ace") -> 3  ("ace")

Dry run

The full table for a = "abcde" (rows) and b = "ace" (columns):

The bold cells are matches, each one more than its diagonal. The answer is the bottom-right cell, 3.

Complexity

• Time: O(m · n). Every cell is filled once in constant time.
• Space: O(m · n) for the table. Each row only needs the previous one, so it can be cut to O(min(m, n)) with two rows.

Edge cases and pitfalls

• An empty string gives 0.
• Identical strings give their full length.
• Subsequence vs substring. A common substring must be contiguous; for that, a mismatch resets the cell to 0 instead of taking the max.
• Off-by-one indexing. dp[i][j] describes a[:i], so compare a[i-1] and b[j-1], not a[i] and b[j].

Related problems

• Edit Distance (LeetCode 72): the same table, minimising edits instead of maximising matches.
• Longest Palindromic Subsequence (LeetCode 516): equivalent to the LCS of a string and its reverse.
• Distinct Subsequences (LeetCode 115): two-string DP that counts matches instead of measuring them.