Longest Common Subsequence (LCS)

What is a subsequence?

A subsequence keeps characters in their original order but may skip some. From "ABCDE":

• "ACE" ✅ (skip B and D)
• "AEC" ❌ (order changed)

A substring is stricter — it must be contiguous ("BCD").

The Longest Common Subsequence (LCS) of two strings is the longest subsequence that appears in both. For "ABCBDAB" and "BDCABA", one LCS is "BCBA" (length 4).

Why dynamic programming?

A string of length m has 2ᵐ subsequences — checking them all is hopeless. But the problem has optimal substructure: the LCS of two strings can be built from the LCS of their prefixes.

Let dp[i][j] = length of the LCS of the first i letters of A and the first j letters of B.

if A[i] == B[j]:   dp[i][j] = dp[i−1][j−1] + 1            (match: extend)
else:              dp[i][j] = max(dp[i−1][j], dp[i][j−1]) (drop a letter from A or B)

Base case: row 0 and column 0 are 0 (an empty string has nothing in common).

In the 3D model, a match lights up the diagonal cell (green), and a mismatch compares the cells above and to the left (yellow). Bar heights equal the LCS lengths, so the table looks like a staircase rising towards the far corner.

Reading the answer

dp[m][n] is the length. To get the actual subsequence, start at the bottom-right cell and walk back:

• if the letters match, that letter is part of the LCS — move diagonally;
• otherwise move to whichever neighbour (up or left) holds the bigger value.

Collect the matched letters in reverse.

Code

def lcs(A, B):
    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])
    # trace back
    i, j, out = m, n, []
    while i > 0 and j > 0:
        if A[i - 1] == B[j - 1]:
            out.append(A[i - 1]); i -= 1; j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return dp[m][n], "".join(reversed(out))

print(lcs("ABCBDAB", "BDCABA"))   # (4, 'BCBA')
print(lcs("AGGTAB", "GXTXAYB"))   # (4, 'GTAB')

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int lcsLength(const string& A, const string& B) {
    int m = A.size(), n = B.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = (A[i - 1] == B[j - 1]) ? dp[i - 1][j - 1] + 1
                                              : max(dp[i - 1][j], dp[i][j - 1]);
    return dp[m][n];
}

int main() {
    cout << lcsLength("ABCBDAB", "BDCABA") << "\n";   // 4
}

Where is LCS used?

• diff and Git: the lines that stay the same form an LCS; everything else is shown as added or removed.
• Bioinformatics: comparing DNA and protein sequences.
• Plagiarism detection and spell-checking (closely related to edit distance).

Related problems

• Longest common substring (contiguous) — similar table, but reset to 0 on a mismatch.
• Edit distance (Levenshtein) — minimum insertions, deletions and substitutions to turn A into B.
• Longest increasing subsequence — a single-sequence cousin.

Common mistakes

• Confusing subsequence (gaps allowed) with substring (no gaps).
• Indexing A[i] instead of A[i − 1] when the table has an extra row and column.
• Expecting a unique answer — there can be several LCSs of the same length.