Bytebook Compiler

Dynamic Programming

Longest Common Subsequence

Find the longest sequence common to two strings: subsequences vs substrings, the LCS table and recurrence, traceback, and the related edit-distance problem.

4 min read2 runnable examplesInteractive4-question quiz

A subsequence keeps characters in order but may skip some: "ACE" is a subsequence of "ABCDE". (A substring must be contiguous.) The longest common subsequence (LCS) of two strings is the longest sequence that is a subsequence of both.

LCS powers diff tools, version control, DNA sequence alignment and plagiarism detection.

Recurrence

State: L[i][j] = length of the LCS of the first i characters of X and the first j characters of Y.

L[i][j] = 0 if i = 0 or j = 0 L[i][j] = L[i−1][j−1] + 1 if X[i] = Y[j] L[i][j] = max(L[i−1][j], L[i][j−1]) otherwise

If the last characters match, they extend the LCS of the shorter prefixes. If not, drop one of them — whichever gives the longer result.

Watch it fill

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

int main() {
    string X = "ABCBDAB", Y = "BDCABA";
    int m = X.size(), n = Y.size();
    vector<vector<int>> L(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            L[i][j] = (X[i - 1] == Y[j - 1]) ? L[i - 1][j - 1] + 1 : max(L[i - 1][j], L[i][j - 1]);

    cout << "    ";
    for (char c : Y) cout << " " << c;
    cout << endl;
    for (int i = 0; i <= m; i++) {
        cout << (i ? X[i - 1] : ' ') << " ";
        for (int j = 0; j <= n; j++) cout << " " << L[i][j];
        cout << endl;
    }

    string lcs;                                         // trace back from the bottom-right corner
    for (int i = m, j = n; i > 0 && j > 0; ) {
        if (X[i - 1] == Y[j - 1]) { lcs += X[i - 1]; i--; j--; }
        else if (L[i - 1][j] >= L[i][j - 1]) i--;
        else j--;
    }
    reverse(lcs.begin(), lcs.end());
    cout << "LCS length " << L[m][n] << ": " << lcs << endl;
    return 0;
}
Output
     B D C A B A
   0 0 0 0 0 0 0
A  0 0 0 0 1 1 1
B  0 1 1 1 1 2 2
C  0 1 1 2 2 2 2
B  0 1 1 2 2 3 3
D  0 1 2 2 2 3 3
A  0 1 2 2 3 3 4
B  0 1 2 2 3 4 4
LCS length 4: BCBA
Try it Yourself

Time and space O(mn). Brute force would check all 2ᵐ subsequences of X.

The edit distance (Levenshtein distance) is the minimum number of single-character insertions, deletions and substitutions that turn one string into another — the basis of spell checkers.

D[i][j] = D[i−1][j−1] if X[i] = Y[j] D[i][j] = 1 + min(D[i−1][j] (delete), D[i][j−1] (insert), D[i−1][j−1] (substitute)) otherwise

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

int editDistance(const string &a, const string &b) {
    vector<vector<int>> D(a.size() + 1, vector<int>(b.size() + 1));
    for (size_t i = 0; i <= a.size(); i++) D[i][0] = i;
    for (size_t j = 0; j <= b.size(); j++) D[0][j] = j;
    for (size_t i = 1; i <= a.size(); i++)
        for (size_t j = 1; j <= b.size(); j++)
            D[i][j] = a[i - 1] == b[j - 1] ? D[i - 1][j - 1]
                    : 1 + min({D[i - 1][j], D[i][j - 1], D[i - 1][j - 1]});
    return D[a.size()][b.size()];
}

int main() {
    cout << "kitten -> sitting: " << editDistance("kitten", "sitting") << endl;
    cout << "sunday -> saturday: " << editDistance("sunday", "saturday") << endl;
    cout << "algorithm -> altruistic: " << editDistance("algorithm", "altruistic") << endl;
    return 0;
}
Output
kitten -> sitting: 3
sunday -> saturday: 3
algorithm -> altruistic: 6
Try it Yourself

Test yourself

4 questions · pick an answer to check it instantly

  1. 1

    Which is a subsequence of "PROGRAM" but not a substring?

  2. 2

    If X[i] = Y[j], what is L[i][j]?

  3. 3

    What is the LCS length of "ABCBDAB" and "BDCABA"?

  4. 4

    What is the edit distance between "cat" and "cut"?

Esc
↑↓ move↵ open