Blind 75 Visualized

#60 · 2D DP

Longest Common Subsequence

Given two strings, return the length of their longest common subsequence: the longest sequence of characters that appears, in order but not necessarily contiguously, in both.

MediumLeetCode
  • Computing
  • Depends on
  • Answer
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Two-dimensional DP table

dp[i][j] = the LCS length of the suffixes a[i..] and b[j..]. If the two first letters match they can both be used: 1 + dp[i + 1][j + 1]. Otherwise one of them is skipped: the larger of dp[i + 1][j] and dp[i][j + 1]. An extra row and column of zeros stand for empty suffixes.

Memory layout

(m + 1) × (n + 1) integers, row by row.

OperationCost
timeO(m·n)
spaceO(m·n); O(min(m, n)) with two rolling rows

Rolling rows

A cell reads only its right neighbour (same row), the cell below and the diagonal (row below). So two rows suffice, and the shorter string can define the row length.

Memory layout

Two arrays of length min(m, n) + 1, swapped after each row.

OperationCost
spaceO(min(m, n))

Why it fits

  • Whether the first letters match decides whether the problem shrinks by one letter in both strings or by one in either: always a smaller instance of the same question.
  • The sub-problems are pairs of suffixes, so there are only (m + 1)(n + 1) of them; the table stores each once.
  • Every cell depends on three neighbours, so rows can be discarded as soon as the next row is done.

Why alternatives degrade

Enumerating all subsequences of one string:
A string of length m has 2^m subsequences, and each would need a containment check in the other string.
Longest common substring approach:
A substring must be contiguous; subsequences may skip letters, so the recurrences differ (mismatches reset to 0 for substrings).
Greedy matching:
Matching the first equal pair found can lose a longer common subsequence later (for example "abcde" and "bcae").

Four approaches, from naive to production

1 · beginner

Plain recursion

time O(2^(m+n))space O(m + n) recursion

Compare the first letters of the two remaining suffixes. If they match, count one and move both forward. If not, take the better result of skipping a letter of either string. Stop when either string is exhausted.

int longestCommonSubsequence(string a, string b) {
    function<int(int, int)> lcs = [&](int i, int j) -> int {
        if (i == (int)a.size() || j == (int)b.size()) return 0;
        if (a[i] == b[j]) return 1 + lcs(i + 1, j + 1);
        return max(lcs(i + 1, j), lcs(i, j + 1));
    };
    return lcs(0, 0);
}

Flaws & bottlenecks

  • Pairs of positions are solved many times (lcs(2, 1) is reached through different skip orders).
  • The number of calls grows exponentially in the lengths.
  • Recursion depth m + n.

Interviewer cross-questions

Why can you skip a letter of either string when letters differ?

Say: If a[i] and b[j] differ they cannot both be the next common letter, so at least one of them is not used. Dropping a[i] or dropping b[j] covers both possibilities.

Why take both letters when they match?

Say: Matching them never hurts: an optimal common subsequence can always be rearranged to use the first matching pair (an exchange argument), so recursing with both advanced is safe.

How do you cache?

Say: The state is just (i, j), so a table of (m + 1) × (n + 1) answers removes every repeated call.

2 · intermediate

Memoised recursion

time O(m·n)space O(m·n)

The same recursion with a memo table indexed by (i, j). A cell is computed once; later requests return the stored value.

int longestCommonSubsequence(string a, string b) {
    vector<vector<int>> memo(a.size(), vector<int>(b.size(), -1));
    function<int(int, int)> lcs = [&](int i, int j) -> int {
        if (i == (int)a.size() || j == (int)b.size()) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        int result;
        if (a[i] == b[j]) result = 1 + lcs(i + 1, j + 1);
        else result = max(lcs(i + 1, j), lcs(i, j + 1));
        memo[i][j] = result;
        return result;
    };
    return lcs(0, 0);
}

Flaws & bottlenecks

  • Recursion depth up to m + n, which can overflow the stack for long strings.
  • The memo is a full m × n table of -1 values.
  • Function-call overhead for each cell.

Interviewer cross-questions

How deep can the recursion go?

Say: Each call advances at least one index, so the depth is at most m + n. For strings of a thousand letters that is fine; for millions it is not.

What does the memo buy?

Say: There are only m·n distinct (i, j) pairs, and each is computed once, so the work drops from exponential to O(m·n).

How do you avoid recursion?

Say: Fill the table iteratively from the end of both strings backwards.

3 · advanced

Bottom-up table

time O(m·n)space O(m·n)

Fill dp from the bottom-right: dp[i][j] = 1 + dp[i + 1][j + 1] when the letters match, otherwise max(dp[i + 1][j], dp[i][j + 1]). The extra row and column stay 0. The answer is dp[0][0].

int longestCommonSubsequence(string a, string b) {
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            if (a[i] == b[j]) dp[i][j] = 1 + dp[i + 1][j + 1];
            else dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]);
        }
    }
    return dp[0][0];
}

Flaws & bottlenecks

  • Stores the whole table, but only two rows are ever read.
  • Reports only the length; reconstructing the subsequence needs the table (or a second pass).
  • For two long strings (tens of thousands of letters each) the table does not fit in memory.

Interviewer cross-questions

How do you recover the subsequence itself?

Say: Walk from (0, 0): if the letters match, output the letter and go diagonally; otherwise move to the neighbour (below or right) with the larger value.

Why are the extra row and column zeros?

Say: They represent an empty suffix, which has nothing in common with anything. Starting from zeros removes the base-case branches from the loops.

How would you save memory?

Say: Keep only the row below the one being computed, as the expert approach does.

4 · expert

Two rolling rows

time O(m·n)space O(min(m, n))

Make the second string the shorter one and keep two arrays of its length plus one: the row below (next) and the row being computed (cur). After each row, swap them. The answer is next[0] after the last row.

int longestCommonSubsequence(string a, string b) {
    if (b.size() > a.size()) swap(a, b);
    vector<int> next(b.size() + 1, 0);
    vector<int> cur(b.size() + 1, 0);
    for (int i = (int)a.size() - 1; i >= 0; i--) {
        for (int j = (int)b.size() - 1; j >= 0; j--) {
            cur[j] = a[i] == b[j] ? 1 + next[j + 1] : max(next[j], cur[j + 1]);
        }
        swap(cur, next);
    }
    return next[0];
}

Flaws & bottlenecks

  • The subsequence cannot be reconstructed from two rows (use Hirschberg's divide-and-conquer if you need it in linear space).
  • The swap and the shorter-string trick add subtle code.
  • Reading cur[j + 1] relies on iterating j from right to left.

Interviewer cross-questions

Why swap instead of copying?

Say: Swapping two references is O(1); copying a row costs O(n) per row. After the swap the finished row is reused as the "row below", and the stale array is overwritten.

Why make the second string the shorter one?

Say: The rows have the length of the second string, so memory is O(min(m, n)).

Can you get the actual subsequence in linear space?

Say: Yes, with Hirschberg's algorithm: compute LCS lengths forwards and backwards for the two halves of one string to find where the middle splits, then recurse on both halves.

Synchronized code walkthrough

Showing: Plain recursion — shares the player above; click any step to jump.

int longestCommonSubsequence(string a, string b) {
    function<int(int, int)> lcs = [&](int i, int j) -> int {
        if (i == (int)a.size() || j == (int)b.size()) return 0;
        if (a[i] == b[j]) return 1 + lcs(i + 1, j + 1);
        return max(lcs(i + 1, j), lcs(i, j + 1));
    };
    return lcs(0, 0);
}