Longest Common Subsequence

A subsequence preserves order but need not be contiguous. Given sequences $X$ and $Y$, the LCS problem asks for a maximum-length sequence that is a subsequence of both.

Let $dp[i][j]$ be the LCS length of prefixes $X[:i]$ and $Y[:j]$:

$$dp[i][j] = \begin{cases} dp[i-1][j-1]+1, & X[i-1]=Y[j-1],\\ \max(dp[i-1][j],dp[i][j-1]), & \text{otherwise}. \end{cases}$$

Empty-prefix rows and columns are zero.

def lcs_length(left: str, right: str) -> int:
    previous = [0] * (len(right) + 1)
    for left_item in left:
        current = [0]
        for j, right_item in enumerate(right, start=1):
            if left_item == right_item:
                current.append(previous[j - 1] + 1)
            else:
                current.append(max(previous[j], current[-1]))
        previous = current
    return previous[-1]

Cost and output

• Full table: $O(mn)$ time and $O(mn)$ space.
• Length only: $O(mn)$ time and $O(\min(m,n))$ space after choosing the shorter sequence as the row width.
• Reconstructing an LCS requires retained choices, a full table, or a more specialized divide-and-conquer reconstruction.

The longest common substring is a different problem because matching symbols must be contiguous.

Source

• MIT OpenCourseWare: Dynamic Programming II