Longest Common Subsequence

git diff, plagiarism checkers and DNA alignment all ask one question: what is the longest sequence that appears, in order, in both inputs? Trying every subsequence is exponential; one table of prefixes answers it in O(m·n).

★ Lecture: DP_LCS · Zaza Gamezardashvili▶ video intermediate⏱ 20 min read

←Builds on

10DP on GridsThe LCS table is a grid over prefixes of the two strings, filled cell by cell.4Generating Subsets & PermutationsA subsequence is a subset of positions; LCS avoids trying all of them.

Leads to→

10Edit DistanceEdit distance fills the same table over two prefixes as LCS, with insert, delete and replace as moves.

1Learn 2Watch 3Play 4Check 5Practice

Learn

The idea, the mechanics and the cost.

01What a subsequence is

A subsequence is what is left after deleting some elements of a sequence while keeping the rest in their original order. The sequence itself counts as its own subsequence too.

Formally, Z = ⟨z₁, z₂, …, z_k⟩ is a subsequence of X = ⟨x₁, x₂, …, x_n⟩ if there is a strictly increasing sequence of indices i₁ < i₂ < … < i_k such that z_j = x_{i_j} for every j = 1, …, k.

The lecture’s example: Z = ⟨B, C, D, B⟩ is a subsequence of X = ⟨A, B, C, B, D, A, B⟩ with index sequence ⟨2, 3, 5, 7⟩.

Do not confuse it with a substring, which must be contiguous. “BCD” is not a substring of ABCBDAB (the B in between breaks it), but it is a subsequence. That freedom to skip is exactly what makes the problem interesting.

02Common, longest, and too many to try

Z is a common subsequence of X and Y if it is a subsequence of both. For X = ⟨A, B, C, B, D, A, B⟩ and Y = ⟨B, D, C, A, B, A⟩, ⟨B, C, A⟩ is common (length 3), but ⟨B, C, B, A⟩ is longer: length 4, and nothing longer exists. ⟨B, D, A, B⟩ also has length 4: the longest common subsequence (LCS) need not be unique.

Brute force would list every subsequence of X and test it against Y. A sequence of length m has 2ᵐ subsequences, one per subset of {1, 2, …, m}, so this is exponential.

The way out is to look at prefixes. The prefix of length i is Xᵢ = ⟨x₁, …, xᵢ⟩, for i from 0 to m. Here X₄ = ⟨A, B, C, B⟩, and X₀ is empty. The subproblems will be: the LCS of a prefix of X and a prefix of Y. There are only (m+1)(n+1) of them.

03The theorem: look at the last letters

Let Z = ⟨z₁, …, z_k⟩ be an LCS of X = ⟨x₁, …, x_m⟩ and Y = ⟨y₁, …, y_n⟩. Then:

if xₘ = yₙ, then z_k = xₘ = yₙ and Z_{k−1} is an LCS of X_{m−1} and Y_{n−1};
if xₘ ≠ yₙ and z_k ≠ xₘ, then Z is an LCS of X_{m−1} and Y;
if xₘ ≠ yₙ and z_k ≠ yₙ, then Z is an LCS of X and Y_{n−1}.

So the LCS of two sequences contains an LCS of their prefixes: the problem has optimal substructure. Finding it reduces to one subproblem (equal last letters: solve X_{m−1}, Y_{n−1} and append the letter) or two (different: solve both and keep the longer).

The subproblems also overlap: both “X_{m−1} with Y” and “X with Y_{n−1}” need “X_{m−1} with Y_{n−1}”. Plain recursion would solve it again and again, so we store every answer in a table.

04The recurrence and the table

Let c[i, j] be the LCS length of the prefixes Xᵢ and Yⱼ. If i or j is 0, one prefix is empty, so c = 0. Otherwise:

c[i, j] = c[i−1, j−1] + 1 if xᵢ = yⱼ;
c[i, j] = max(c[i−1, j], c[i, j−1]) if xᵢ ≠ yⱼ.

Fill the (m+1) × (n+1) table row by row; every cell only needs its upper, left and upper left neighbours, which are already done. The lecture starts on row 1: X[1] = A ≠ Y[1] = B, so c[1][1] = max(c[0][1], c[1][0]) = 0; the same for Y[2] and Y[3]; then X[1] = Y[4] = A, so c[1][4] = c[0][3] + 1 = 1.

When all 42 inner cells are filled, the bottom right corner c[7][6] = 4 is the LCS length of the whole sequences. Each cell takes O(1), so filling costs O(m·n).

The coloured cells are the walk back from the corner; green ones contribute a letter.

05Recovering the LCS, and the cost

The table gives the length; the sequence comes from walking back from c[m][n]:

if xᵢ = yⱼ, this letter is in the LCS: write it down and move diagonally to (i−1, j−1);
otherwise move to the larger of the upper and left neighbours.

The letters come out in reverse, so read them backwards at the end. Each step decreases i, j, or both, so recovery costs O(m + n).

Ties matter. Going up on a tie (as on the slides) gives BCBA; the lecture’s C++ code uses if (arr[i−1][j] > arr[i][j−1]) i--; else j--;, which goes left on a tie and finds BDAB. Both are correct: different longest common subsequences of the same length.

Memory is O(m·n) for the table. If you need only the length, two rows are enough. And compare costs: two strings of length 20 need 441 cells, versus 2²⁰ ≈ a million subsequences for brute force.

The lecture's C++C++

Slide 17: the double loop fills the arr table, then the while loop walks back from arr[m][n] and rebuilds the subsequence itself, one matching character at a time.

#include <bits/stdc++.h>
using namespace std;
void lcs(string S1, string S2, int m, int n) {
    int arr[m + 1][n + 1];
    for (int i = 0; i <= m; i++) {
        for (int j=0; j <= n; j++) {
            if (i==0 || j==0) arr[i][j] = 0;
            else if (S1[i-1]==S2[j-1]) arr[i][j]=arr[i-1][j-1]+1;
            else arr[i][j]=max(arr[i-1][j], arr[i][j-1]);
        }
    }
    int index = arr[m][n], i = m, j = n;
    char lcs[index + 1];
    lcs[index] = '\0';
    while (i > 0 && j > 0) {
        if (S1[i - 1] == S2[j - 1]) {
            lcs[index - 1] = S1[i - 1];
            i--;   j--;    index--;
        }
        else if (arr[i - 1][j] > arr[i][j - 1]) i--;
        else j--;
    }
    cout<<"S1: "<<S1<<"\nS2: "<<S2<<"\nLCS: "<<lcs<<"\n";
}
int main() {
    string S1 = "ACADB";  string S2 = "ACBDAB";
    int m = S1.size();  int n = S2.size();
    lcs(S1, S2, m, n);
}

Cost at a glance

Fill the tableO(m·n)

Recover one LCSO(m + n)

Length only, two rowsO(min(m, n)) memory

Brute forceO(2ᵐ · n)

Remember

Subproblems are pairs of prefixes: c[i][j] = LCS length of Xᵢ and Yⱼ, with 0 on the border.
Compare the last letters: equal means diagonal + 1, different means the max of the upper and left cells.
Walk back from the corner to recover one LCS in O(m + n); the tie rule decides which of several LCSs you get.

Watch

The lecture as a narrated explainer video.

▶

Watch the lecture, animated

The video follows the lecture slide by slide: the same example, the same notation. Use it before or after playing with the visualizer.

▶ Open the video page ▣ Open as presentation

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: The default run is the lecture’s X = ABCBDAB, Y = BDCABA. Watch each cell take ↖ on a match or the larger of ↑ / ←, then the walk back spells B C B A. Try the lecture code’s pair ACADB / ACBDAB.

Interactive visualizerfocus here, then space ← →

DP table: X = ABCBDAB, Y = BDCABA

i\\j	1:B	2:D	3:C	4:A	5:B	6:A
0	0	0	0	0	0	0
1:A	·	·	·	·	·	·
2:B	·	·	·	·	·	·
3:C	·	·	·	·	·	·
4:B	·	·	·	·	·	·
5:D	·	·	·	·	·	·
6:A	·	·	·	·	·	·
7:B	·	·	·	·	·	·

LCS output

(empty so far)

Base case: row 0 and column 0 are 0, since an empty prefix shares nothing.

Pseudocode

 1 c[i][0] = c[0][j] = 0   // empty prefix 2 for i in 1..m: for j in 1..n: 3   if X[i] == Y[j]: 4     c[i][j] = c[i-1][j-1] + 1      // ↖ 5   else: 6     c[i][j] = max(c[i-1][j], c[i][j-1])  // ↑ or ← 7 reconstruct: follow arrows from c[m][n]

1 / 1

Check

Three questions. Pick an answer to see why.

X = ABCB, Y = BDCB. You already know c[3][3] = 2. What is c[4][4]?

Which of these is a subsequence of ABCBDAB but NOT a substring of it?

During reconstruction xᵢ ≠ yⱼ and the upper and left neighbours are equal. What happens?

Practice

Real problems to lock it in, easiest first.

LeetCodeLongest Common Subsequence intermediate↗CSESLongest Common Subsequence intermediate↗LeetCodeDelete Operation for Two Strings intermediate↗LeetCodeShortest Common Supersequence advanced↗

i\\j	1:B	2:D	3:C	4:A	5:B	6:A
0	0	0	0	0	0	0
1:A	·	·	·	·	·	·
2:B	·	·	·	·	·	·
3:C	·	·	·	·	·	·
4:B	·	·	·	·	·	·
5:D	·	·	·	·	·	·
6:A	·	·	·	·	·	·
7:B	·	·	·	·	·	·

i\\j	1:B	2:D	3:C	4:A	5:B	6:A
0	0	0	0	0	0	0
1:A	·	·	·	·	·	·
2:B	·	·	·	·	·	·
3:C	·	·	·	·	·	·
4:B	·	·	·	·	·	·
5:D	·	·	·	·	·	·
6:A	·	·	·	·	·	·
7:B	·	·	·	·	·	·

i\\j	1:B	2:D	3:C	4:A	5:B	6:A
0	0	0	0	0	0	0
1:A	·	·	·	·	·	·
2:B	·	·	·	·	·	·
3:C	·	·	·	·	·	·
4:B	·	·	·	·	·	·
5:D	·	·	·	·	·	·
6:A	·	·	·	·	·	·
7:B	·	·	·	·	·	·