LCS

Longest Common Subsequence

Pattern · two-sequence 2-D table Core DP1 lecture topic O(nm) 4difficulty
Question — exam style

Given two sequences X[1…n] and Y[1…m], a common subsequence is a sequence of characters appearing in both, in the same left-to-right order but not necessarily contiguously. For example, for X = BCDB and Y = ABDC, the string BD is a common subsequence of length 2. Design a dynamic-programming algorithm for the following task.

Input:Two sequences X[1..n] and Y[1..m].
Output:The length of the longest common subsequence of X and Y.

Model answer

4-part format
aSubproblem in words
L(i, j) = the length of the longest common subsequence of the prefixes X[1..i] and Y[1..j], for 0 ≤ i ≤ n and 0 ≤ j ≤ m.

Note the CS6515 convention: LCS uses the plain-prefix subproblem — it does not force the last characters to be used. That "must include the last element" phrasing belongs to LIS, not LCS.

bRecurrence math only, with base cases + bounds
L(i, 0) = 0 for 0 ≤ i ≤ n L(0, j) = 0 for 0 ≤ j ≤ m If X[i] = Y[j]: L(i, j) = 1 + L(i-1, j-1) Else: L(i, j) = max{ L(i-1, j), L(i, j-1) } for 1 ≤ i ≤ n, 1 ≤ j ≤ m

If the two current characters match, they extend the LCS of the smaller prefixes by 1. If they don't match, at least one of them is unused, so drop X[i] or Y[j] and take the better. All referenced cells have strictly smaller indices — well-defined, no self-reference.

cImplementation analysis
(1) # of subproblems
O(nm)
(2) Time to fill table
O(nm) — O(1) per entry
(3) Where answer is extracted
L(n, m)
(4) Time to extract
O(1)
The tell for a 2-D "align two inputs" table

Whenever a problem gives you two sequences/strings to match up, reach for T(i,j) indexed by a prefix of each, with the answer at the far corner T(n,m). Edit distance, sequence alignment (DPV 6.26), and longest common substring (DPV 6.8) are all this same engine with different cell rules.

Optional pseudocode not required by Ed #9

A mechanical translation of the recurrence. The exam grades the recurrence, not this.

function LCS(X[1..n], Y[1..m]):
    for i = 0 to n: L[i][0] = 0
    for j = 0 to m: L[0][j] = 0
    for i = 1 to n:
        for j = 1 to m:
            if X[i] == Y[j]:
                L[i][j] = 1 + L[i-1][j-1]
            else:
                L[i][j] = max(L[i-1][j], L[i][j-1])
    return L[n][m]
✎

Try it yourself

worked example + self-test

Match → 1+L(i−1,j−1) (diagonal); mismatch → max{above, left}. Answer L(n,m).

Worked full grid shown

X = AGGTAB Y = GXTXAYB

ε G X T X A Y B ε 0 0 0 0 0 0 0 0 A 0 0 0 0 0 1 1 1 G 0 1 1 1 1 1 1 1 G 0 1 1 1 1 1 1 1 T 0 1 1 2 2 2 2 2 A 0 1 1 2 2 3 3 3 B 0 1 1 2 2 3 3 4
Answer: L(6,7) = 4 (bottom-right). One LCS: GTAB (trace back diagonally on matches).
Self-test build the grid, then reveal

X = BCDB Y = ABDCB

Reveal answer
LCS length = 3, e.g. BCB (also BDB is valid).