Longest Common Subsequence

1. Problem & Core Objective

Return the length of the longest subsequence common to two strings. A subsequence keeps relative order but need not be contiguous.

text1 = "abcde", text2 = "ace"    →  3      "ace"
text1 = "abc",   text2 = "abc"    →  3
text1 = "abc",   text2 = "def"    →  0

Constraints: 1 <= text1.length, text2.length <= 1000 · lowercase letters

What's actually being tested: the canonical two-sequence DP — one index per string, with a match/no-match branch. It's the template for Edit Distance, Distinct Subsequences, and Interleaving String, so the shape matters more than the problem.

2. First-Principles Thought Process

One index per string

dp[i][j] = the LCS length of text1's first i characters and text2's first j.

Comparing the last characters of each prefix gives two cases:

They match. That character can be part of the LCS, so take it and recurse on both shorter prefixes:

dp[i][j] = dp[i-1][j-1] + 1

They differ. At least one of them isn't in the LCS, so try dropping each:

dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Why a match doesn't need the max

When the characters match, taking them is never worse than dropping one. Any common subsequence that omits this matching pair can have the pair appended, giving one at least as long.

So dp[i-1][j-1] + 1 is safe without comparing against the alternatives — and skipping that comparison is both faster and a meaningful correctness claim, not just an optimisation.

The base cases are the empty prefixes

dp[0][j] = dp[i][0] = 0 — an empty string shares nothing. Java's zero-initialised arrays give this for free, but it's worth stating.

Indexing offset

dp is over prefix lengths, the strings over positions. So dp[i][j] compares text1.charAt(i-1) with text2.charAt(j-1). That offset is the usual source of bugs.

3. Solution Paths

Approach 1 — Recursion

public int longestCommonSubsequence(String a, String b) {
    return lcs(a, b, a.length(), b.length());
}

private int lcs(String a, String b, int i, int j) {
    if (i == 0 || j == 0) return 0;
    if (a.charAt(i - 1) == b.charAt(j - 1)) return lcs(a, b, i - 1, j - 1) + 1;
    return Math.max(lcs(a, b, i - 1, j), lcs(a, b, i, j - 1));
}

• Time O(2^(m+n)) · Space O(m + n) stack

Counter-questions on this approach

⭐ "Why exponential, and how many distinct states are there?"

Two branches on every mismatch, so up to 2^(m+n) paths. But the state is just (i, j) — only m × n = 10^6 distinct pairs.

That gap is the DP signal, and memoising on (i, j) collapses it directly.

⭐ "Why does the match branch not also consider the alternatives?"

Because taking a matching pair is never worse. Given any common subsequence of a[0..i) and b[0..j) that doesn't use both matching characters, you can append them to get one at least as long.

So dp[i-1][j-1] + 1 dominates, and comparing against dp[i-1][j] and dp[i][j-1] would be redundant work that can't change the answer.

It's an exchange argument, and it's the reason this problem is O(m·n) rather than needing three-way maxima everywhere.

Approach 2 — 2-D tabulation

public int longestCommonSubsequence(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];             // row/col 0 = empty prefix, all zeros

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1))
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }

    return dp[m][n];
}

Trace — a = "abcde", b = "ace" (rows a, columns b):

Answer dp[5][3] = 3 ✓ — the LCS is "ace"

• Time O(m · n) = 10^6 · Space O(m · n) ≈ 4 MB

Counter-questions on this approach

⭐ "Why is the array (m+1) × (n+1)?"

To hold the empty-prefix base cases in row 0 and column 0. Without them, dp[1][1] would read out of bounds.

And it makes the indexing uniform: dp[i][j] always means "first i and first j characters", with i = 0 meaning none.

⭐ "Why charAt(i-1) rather than charAt(i)?"

Because dp is indexed by prefix length while the string is indexed by position. dp[i] concerns the first i characters, whose last one is at index i−1.

It's the same offset as in Decode Ways, and I'd trace i = 1, j = 1 explicitly to confirm it.

"Why does the fill order work?"

dp[i][j] reads the cell above, the cell left, and the diagonal — all with smaller indices. Row-major, left to right, has all three ready.

Approach 3 — Rolled to two rows (optimal)

public int longestCommonSubsequence(String a, String b) {
    if (a.length() < b.length()) { String t = a; a = b; b = t; }   // shorter is the row

    int m = a.length(), n = b.length();
    int[] prev = new int[n + 1], cur = new int[n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) cur[j] = prev[j - 1] + 1;
            else                                     cur[j] = Math.max(prev[j], cur[j - 1]);
        }
        int[] t = prev; prev = cur; cur = t;        // swap, don't allocate
    }
    return prev[n];
}

• Time O(m · n) · Space O(min(m, n))

Counter-questions on this approach

⭐ "Why two rows rather than one?"

Because the recurrence needs the diagonal dp[i-1][j-1], which a single rolled row destroys — by the time you reach column j, position j-1 has already been overwritten with the current row's value.

Unique Paths rolled to one row because it needed only above and left, both of which survive. Needing the diagonal is what forces two rows.

You can do it with one row plus a single saved variable holding the old dp[j-1] — a common trick — but two rows is clearer and the memory difference is negligible.

⭐ "Why swap the arrays rather than copying?"

prev = cur.clone() would be O(n) per row, adding a whole factor. Swapping references is O(1), and the old prev becomes the scratch space for the next row.

The stale values in it are all overwritten before being read, since every cur[j] for j >= 1 is assigned — worth confirming rather than assuming, because a partially-written buffer would silently carry old data.

"Why is cur[0] never assigned?"

It's 0 from initialisation and must stay 0 — the empty prefix of b. Since the inner loop starts at j = 1, it's never touched. That's the base case surviving the roll.

"Why swap so the shorter string is the row?"

Space becomes O(min(m,n)) instead of O(n). With a 1000-character and a 10-character string that's 11 ints rather than 1001.

The LCS is symmetric, so swapping the arguments doesn't change the answer.

"Can this be rolled to O(1)?"

No. The recurrence reads a full row of previous values, not a fixed window — same reason Word Break can't be rolled to scalars. O(min(m,n)) is the floor for this formulation.

Comparison

4. Why the Optimal Wins

The recursion re-explores (i, j) pairs exponentially often when only 10^6 exist.

Rolling to two rows is possible because the recurrence reads only the previous row plus the current row's left neighbour. It can't go to one row because of the diagonal — which is exactly the distinction from Unique Paths.

The framing worth keeping:

One index per string. Characters match → take the diagonal plus one, no comparison needed. They differ → drop one and take the better. The diagonal dependency is why this rolls to two rows rather than one.

5. Java Prerequisites

The two-sequence recurrence

if (a.charAt(i-1) == b.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;
else                                 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);

Index offset — dp over prefix lengths, strings over positions, hence charAt(i-1).

Roll by swapping references

int[] t = prev; prev = cur; cur = t;     // O(1); clone() would be O(n) per row

Swap the arguments so the shorter string drives the row length.

6. Interview Communication Guide

Clarifying questions: Subsequence or substring (subsequence — non-contiguous)? Return the length or the string (length; reconstruction needs the full table)? Case-sensitive (assume yes)? Maximum lengths (1000 each, so 10^6 states)?

The pitch

"One index per string: dp[i][j] is the LCS of the first i characters of one and the first j of the other.

Compare the last characters of those prefixes. If they match, that character can be part of the LCS, so take it and recurse on both shorter prefixes — dp[i-1][j-1] + 1.

If they differ, at least one isn't in the LCS, so try dropping each and take the better — max(dp[i-1][j], dp[i][j-1]).

Worth noting that the match branch takes the diagonal without comparing the alternatives. That's not laziness — taking a matching pair is never worse, because any common subsequence omitting it can have the pair appended to get one at least as long. It's an exchange argument.

Base cases are the empty prefixes, which are 0 and come free from Java's zero-initialised arrays.

O(m·n) = 10^6 time. The full table is 4 MB, but the recurrence only reads the previous row plus the current row's left neighbour, so two rows suffice — O(min(m,n)) if I swap so the shorter string drives the row length.

It can't go to one row, because the recurrence needs the diagonal, which a single row destroys once column j-1 is overwritten. That's the difference from Unique Paths, which needed only above and left.

And I swap the two row references rather than cloning — cloning would add an O(n) cost per row."

Edge cases to volunteer:

Name "abc" / "def". It must return 0 rather than crashing or returning 1 — the whole table stays zero, which confirms the base cases and the mismatch branch both work.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the subsequence itself, not its length."

You need the full table — walk back from dp[m][n], moving diagonally when characters match and otherwise toward the larger of above/left. O(m·n) space, so the rolling optimisation is forfeited.

Same trade as everywhere: O(1)-ish space and reconstruction are mutually exclusive.

⭐ "Find the longest common SUBSTRING instead."

Different recurrence: dp[i][j] = dp[i-1][j-1] + 1 on a match and 0 on a mismatch, since contiguity breaks. The answer is max(dp) rather than dp[m][n]. One-character change in the else branch, completely different meaning.

"Compute the edit distance between the strings."

Question 9. Same two-index shape; the else branch becomes a three-way min over insert, delete and replace. LCS is the template.

"What if there were three strings?"

dp[i][j][k] — O(n³) time and space. At n = 1000 that's 10^9 cells, infeasible. The shape generalises; the cost doesn't.

"What if the alphabet were huge and the strings mostly distinct?"

The Hunt–Szymanski algorithm runs in O((r + n) log n) where r is the number of matching pairs — much faster when matches are sparse. It's what diff uses.

"Find the shortest common supersequence."

m + n − LCS(a,b). A direct corollary: the supersequence contains both strings, overlapping exactly on their LCS. Nice to know, since it looks like a separate problem.