Longest Common Subsequence

Longest Common Subsequence

A subsequence is what's left after deleting some characters from a string without reordering the rest: "ace" is a subsequence of "abcde", but "aec" isn't. The longest common subsequence (LCS) of two strings is the longest string that's a subsequence of both:

s = "ABCBDAB"
t = "BDCABA"          LCS length 4 — e.g. "BCBA" or "BDAB"

LCS is the model problem for two-sequence DP, where the state is a pair of positions, one in each string. The same table shape solves edit distance, diff tools, DNA alignment, shortest common supersequence and several palindrome problems.

Building the recurrence

Let dp[i][j] = the LCS length of the first i characters of s and the first j characters of t. Look at the last character of each prefix:

• They match (s[i-1] == t[j-1]): that character can end the common subsequence, so dp[i][j] = dp[i-1][j-1] + 1.
• They differ: at least one of them isn't in the LCS, so drop one or the other and take the better result: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
• Base case: an empty prefix has an LCS of 0, so row 0 and column 0 are 0.

int lcs(String s, String t) {
    int m = s.length(), n = t.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = s.charAt(i - 1) == t.charAt(j - 1)
                    ? dp[i - 1][j - 1] + 1
                    : Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
}

O(m × n) time and space. Using a table one larger than the strings, with row and column 0 standing for "empty prefix", removes all boundary checks.

Why taking the match greedily is safe

When the last characters match, could skipping the match ever do better? No. Any common subsequence of the two prefixes can be changed to end with that matching character without getting shorter, so dp[i-1][j-1] + 1 is always at least as good as the alternatives.

Recovering the subsequence itself

Walk back from dp[m][n]. On a match, take the character and move diagonally. Otherwise, move toward the neighbour holding the larger value:

String lcsString(String s, String t, int[][] dp) {
    StringBuilder out = new StringBuilder();
    int i = s.length(), j = t.length();
    while (i > 0 && j > 0) {
        if (s.charAt(i - 1) == t.charAt(j - 1)) { out.append(s.charAt(i - 1)); i--; j--; }
        else if (dp[i - 1][j] >= dp[i][j - 1]) i--;
        else j--;
    }
    return out.reverse().toString();
}

When several LCSs exist, the tie-breaking rule decides which one you get.

Saving memory

Each row only needs the previous row, so two rows (or one row plus a variable holding the old diagonal value) give O(min(m, n)) space:

int lcsTwoRows(String s, String t) {
    if (t.length() > s.length()) { String x = s; s = t; t = x; }      // make t the shorter string
    int[] prev = new int[t.length() + 1], cur = new int[t.length() + 1];
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 1; j <= t.length(); j++)
            cur[j] = s.charAt(i - 1) == t.charAt(j - 1) ? prev[j - 1] + 1 : Math.max(prev[j], cur[j - 1]);
        int[] tmp = prev; prev = cur; cur = tmp;
    }
    return prev[t.length()];
}

The trade-off: with only two rows you can no longer walk back to recover the subsequence. Hirschberg's algorithm recovers it in linear space, but that's rarely expected.

The family

Edit distance (Levenshtein)

The minimum number of single-character insertions, deletions and substitutions to turn s into t. It uses the same table, but minimizes operations:

int editDistance(String s, String t) {
    int m = s.length(), n = t.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;         // delete all i characters
    for (int j = 0; j <= n; j++) dp[0][j] = j;         // insert all j characters
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = s.charAt(i - 1) == t.charAt(j - 1)
                    ? dp[i - 1][j - 1]                                   // nothing to do
                    : 1 + Math.min(dp[i - 1][j - 1],                     // substitute
                               Math.min(dp[i - 1][j], dp[i][j - 1]));   // delete from s / insert into s
    return dp[m][n];
}

It's used in spell checkers, fuzzy search ("did you mean…"), and DNA sequence comparison.

Longest common substring (contiguous)

Substrings must be contiguous, so a mismatch resets the run to 0 instead of carrying the best result forward:

if (s.charAt(i - 1) == t.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; best = Math.max(best, dp[i][j]); }
else dp[i][j] = 0;

The answer is the maximum anywhere in the table, not dp[m][n]. Confusing subsequence with substring is a common interview mistake, so ask which one is meant.

Derived problems: one line on top of LCS

• Minimum deletions to make two strings equal: m + n − 2·LCS.
• Shortest common supersequence (the shortest string containing both as subsequences): length m + n − LCS, and you build it by walking the LCS table and emitting unmatched characters from both sides.
• Longest palindromic subsequence of s = LCS(s, reverse(s)).
• Minimum insertions to make s a palindrome = n − LPS(s).
• Longest increasing subsequence can be seen as LCS(array, sorted distinct array), although the dedicated O(n log n) algorithm is better.

Where you'll meet it outside interviews

diff and version-control tools compute line-level LCS or edit scripts (usually with Myers' O((m+n)·D) algorithm, where D is the number of differences) to show what changed. Bioinformatics aligns DNA and protein sequences with weighted variants such as Needleman–Wunsch and Smith–Waterman. Plagiarism and near-duplicate detection compare token sequences.

Follow-up questions this topic invites — and their answers

Q: What's the difference between the longest common subsequence and the longest common substring? A: A subsequence may skip characters, while a substring must be contiguous. In the DP, a mismatch carries forward the best of the neighbours for a subsequence, but resets to 0 for a substring. For a substring the answer is the table's maximum rather than its last cell.

Q: How do you reduce LCS to O(n) space? A: Each row depends only on the previous row, so keep two rows (or one row plus the previous diagonal value) and put the shorter string on the inner loop. You lose the ability to reconstruct the subsequence by backtracking unless you use Hirschberg's divide-and-conquer technique.

Q: How is edit distance related to LCS? A: With only insertions and deletions allowed (no substitutions), edit distance equals m + n − 2·LCS. Adding substitution changes the recurrence: a mismatch takes the minimum of substitute, insert and delete, each costing 1.

Q: What if the strings are very long, say millions of characters? A: O(m·n) becomes infeasible. Practical tools use algorithms that exploit similarity (Myers' diff runs in O((m+n)·D) and is fast when the inputs differ little), heuristics, or line-level rather than character-level comparison.

Q: How would you compute the LCS of three strings? A: Extend the state to three indexes: dp[i][j][k], adding 1 when all three characters match, and otherwise taking the maximum of dropping each one. That's O(m·n·p) time. LCS of many strings is NP-hard in general.