237. Longest Common Subsequence

Why this mechanism works

Let each axis represent a prefix length, with row zero and column zero as empty prefixes. If the final characters match, a common subsequence can extend the diagonal answer by one. Otherwise at least one final character must be omitted, so take the better answer after dropping either side.

State and boundaries

dp[i][j] is the LCS length for first[:i] and second[:j]. Smaller prefix pairs are solved before the current pair.

Protocol

1. Allocate an (m+1)-by-(n+1) zero table.
2. Scan positive prefix lengths.
3. On equal final characters use diagonal+1.
4. Otherwise use max(top,left).
5. Return dp[m][n].

Visualization

first abcde, second ace
match a, skip b, match c, skip d, match e
subsequence 'ace' has length 3 without requiring adjacency

Python implementation

def lcs_length(first, second):
    m, n = len(first), len(second)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if first[i - 1] == second[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[m][n]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 lcs_length: m, n = len(first), len(second)
first='abcde'; second='ace'; m=5; n=3

L3 lcs_length: dp = [[0] * (n + 1) for _ in range(m + 1)]
first='abcde'; second='ace'; m=5; n=3; _=0

L3 lcs_length: dp = [[0] * (n + 1) for _ in range(m + 1)]
first='abcde'; second='ace'; m=5; n=3; _=1

L3 lcs_length: dp = [[0] * (n + 1) for _ in range(m + 1)]
first='abcde'; second='ace'; m=5; n=3; _=2

L3 lcs_length: dp = [[0] * (n + 1) for _ in range(m + 1)]
first='abcde'; second='ace'; m=5; n=3; _=3

L3 lcs_length: dp = [[0] * (n + 1) for _ in range(m + 1)]
first='abcde'; second='ace'; m=5; n=3; _=4

L3 lcs_length: dp = [[0] * (n + 1) for _ in range(m + 1)]
first='abcde'; second='ace'; m=5; n=3; _=5

L3 lcs_length: dp = [[0] * (n + 1) for _ in range(m + 1)]
first='abcde'; second='ace'; m=5; n=3; dp=[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

... 31 intermediate state changes omitted ...

L5 lcs_length: for j in range(1, n + 1):
first='abcde'; second='ace'; m=5; n=3; dp=[[0, 0, 0, 0], [0, 1, 1, 1], [0, 1, 1, 1], [0, 1, 2, 2], [0, 1, 2, 2], [0, 1, 0, 0]]; i=5; j=2

L9 lcs_length: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
first='abcde'; second='ace'; m=5; n=3; dp=[[0, 0, 0, 0], [0, 1, 1, 1], [0, 1, 1, 1], [0, 1, 2, 2], [0, 1, 2, 2], [0, 1, 2, 0]]; i=5; j=2

L5 lcs_length: for j in range(1, n + 1):
first='abcde'; second='ace'; m=5; n=3; dp=[[0, 0, 0, 0], [0, 1, 1, 1], [0, 1, 1, 1], [0, 1, 2, 2], [0, 1, 2, 2], [0, 1, 2, 0]]; i=5; j=3

L7 lcs_length: dp[i][j] = dp[i - 1][j - 1] + 1
first='abcde'; second='ace'; m=5; n=3; dp=[[0, 0, 0, 0], [0, 1, 1, 1], [0, 1, 1, 1], [0, 1, 2, 2], [0, 1, 2, 2], [0, 1, 2, 3]]; i=5; j=3

L2 lcs_length: m, n = len(first), len(second)
first='abc'; second='def'; m=3; n=3

L3 lcs_length: dp = [[0] * (n + 1) for _ in range(m + 1)]
first='abc'; second='def'; m=3; n=3; _=0

L3 lcs_length: dp = [[0] * (n + 1) for _ in range(m + 1)]
first='abc'; second='def'; m=3; n=3; _=1

L3 lcs_length: dp = [[0] * (n + 1) for _ in range(m + 1)]
first='abc'; second='def'; m=3; n=3; _=2

L3 lcs_length: dp = [[0] * (n + 1) for _ in range(m + 1)]
first='abc'; second='def'; m=3; n=3; _=3

L3 lcs_length: dp = [[0] * (n + 1) for _ in range(m + 1)]
first='abc'; second='def'; m=3; n=3; dp=[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

L4 lcs_length: for i in range(1, m + 1):
first='abc'; second='def'; m=3; n=3; dp=[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]; i=1

L5 lcs_length: for j in range(1, n + 1):
first='abc'; second='def'; m=3; n=3; dp=[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]; i=1; j=1

... 6 intermediate state changes omitted ...

L4 lcs_length: for i in range(1, m + 1):
first='abc'; second='def'; m=3; n=3; dp=[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]; i=3; j=3

L5 lcs_length: for j in range(1, n + 1):
first='abc'; second='def'; m=3; n=3; dp=[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]; i=3; j=1

L5 lcs_length: for j in range(1, n + 1):
first='abc'; second='def'; m=3; n=3; dp=[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]; i=3; j=2

L5 lcs_length: for j in range(1, n + 1):
first='abc'; second='def'; m=3; n=3; dp=[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]; i=3; j=3

Why the solution is correct

Empty prefixes share only an empty subsequence. Matching endpoints admit an optimum ending with that common character, reducing to the two shorter prefixes. With unequal endpoints, no common subsequence can use both as its final matched pair, so an optimum omits at least one and is covered by top or left.

Time and space

O(m*n) time and O(m*n) auxiliary table space.

Common mistakes

Resetting to zero on mismatch computes longest common substring, a different problem. Table indices are prefix lengths, so character indices are one smaller.

Reasoning card

Transfer exercise

Backtrack through the table to reconstruct one LCS, with an explicit tie rule when top and left are equal.