Longest Common Subsequence

git diff telling you which lines changed between two file versions, and a bioinformatics tool aligning two DNA strands, are solving the same underlying problem: given two sequences, what is the longest subsequence — elements in the same relative order, but not necessarily adjacent — that both share? That's the longest common subsequence (LCS), and it's the template that the edit-distance family of problems is built on top of.

The idea: a 2D table, one decision per cell

Define $dp[i][j]$ as the LCS length using the first $i$ characters of string $A$ and the first $j$ characters of string $B$. Two cases, driven entirely by whether the current characters match:

$$dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } A_i = B_j \\ \max(dp[i-1][j],\ dp[i][j-1]) & \text{if } A_i \ne B_j \end{cases}$$

In words: if the last characters of both prefixes match, they must belong in the LCS together, so take the best answer without them and add one. If they don't match, at least one of the two characters is useless for this particular ending, so take the better of dropping either one. This is $O(mn)$ time and space for strings of length $m$ and $n$ — a table with one row per character of $A$ and one column per character of $B$.

Worked example: LCS of "ABC" and "AC"

Table rows for $B$ = "AC" prefixes 0,1,2, columns for $A$ = "ABC" prefixes 0,1,2,3, dp[0][*] = dp[*][0] = 0. $A_1{=}'A', B_1{=}'A'$: match, $dp[1][1] = dp[0][0]+1 = 1$. $A_2{=}'B', B_1{=}'A'$: no match, $dp[2][1] = \max(dp[1][1], dp[2][0]) = \max(1,0) = 1$. $A_2{=}'B', B_2{=}'C'$: no match, $dp[2][2] = \max(dp[1][2], dp[2][1])$; need $dp[1][2]$: $A_1{=}'A', B_2{=}'C'$, no match, $=\max(dp[0][2],dp[1][1])=\max(0,1)=1$; so $dp[2][2]=\max(1,1)=1$. $A_3{=}'C', B_2{=}'C'$: match, $dp[3][2] = dp[2][1]+1 = 1+1=2$. Final LCS length is 2 ("AC").

def lcs(a, b):                          # O(m*n) time and space
    m, n = len(a), len(b)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+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[m][n]

Where it shows up

Interview staples: longest common subsequence itself, and it's the backbone underneath Edit Distance and shortest common supersequence. On a desk, LCS-style alignment underlies diffing tool implementations, comparing two versions of a strategy's trade log or two related time series for structural similarity, and sequence-alignment tasks borrowed directly from bioinformatics tooling used in some alternative-data pipelines.