Longest Common Subsequence

LCS works by observing that the answer for two strings decomposes into a smaller identical subproblem: either the last characters match — in which case they must both belong to the optimal subsequence, so the answer is 1 + LCS of the remaining prefixes — or they don't, in which case the optimal subsequence discards the last character of one of the strings, so the answer is the max of the two ways to drop one character. This overlapping-subproblem recursion is what makes it a textbook 2D dynamic programming problem.

Problem

Given strings s1, s2, find the length of the longest sequence of characters that appears in both, in the same relative order but not necessarily contiguous.

Example: s1="abdca", s2="cbda" → LCS = "bda", length 3.

Recognize the pattern

• Two sequences compared for order-preserving similarity, not exact substring match.
• Keywords: "subsequence" (skips allowed), "common", edit-distance-style, shortest-common-supersequence, diff-tool problems.
• Recurrence naturally indexes by a pair (i, j) — two pointers over two strings — a hallmark of 2D DP.

Brute force → optimal

Brute force: recurse on index pair (i, j): if the last characters match, take them and recurse on (i-1, j-1); otherwise try dropping the last char of either string and take the best.

lcs(i, j):
  if i == 0 or j == 0: return 0
  if s1[i-1] == s2[j-1]: return 1 + lcs(i-1, j-1)
  return max(lcs(i-1, j), lcs(i, j-1))

Cost: each call spawns up to 2 children with no reuse of shared subproblems → O(2^(m+n)) time, O(m+n) recursion stack.

Optimal: the pair (i, j) only ever takes O(m·n) distinct values, so memoize (top-down) or fill a table bottom-up: dp[i][j] = LCS length of s1[0..i) and s2[0..j).

dp[i][j] = dp[i-1][j-1] + 1              if s1[i-1] == s2[j-1]
dp[i][j] = max(dp[i-1][j], dp[i][j-1])   otherwise

Complexity, derived

The table has (m+1)×(n+1) cells; each cell does O(1) work (one character comparison, one addition or max) once its two or three neighbors are known — so total work is exactly the cell count: O(m·n) time. Space for the full table is O(m·n); since row i only reads row i-1, this collapses to O(min(m,n)) if only the length (not the actual subsequence) is needed by keeping two rolling rows.

Worked example

s1 = "abdca" (m=5), s2 = "cbda" (n=4). Rows = s1 index i (0..5), cols = s2 index j (0..4). Table (dp[i][j]):

dp[5][4] = 3, matching the expected "bda". Trace back from (5,4), where the row index tracks how much of s1 (a,b,d,c,a) has been consumed and the column index tracks s2 (c,b,d,a): s1[4]='a', s2[3]='a' match → take 'a', move diagonally to (4,3). At (4,3), s1[3]='c', s2[2]='d' mismatch, so compare the neighbors dp[3][3]=2 and dp[4][2]=1; the larger is dp[3][3], so move up to (3,3) without taking a character. At (3,3), s1[2]='d', s2[2]='d' match → take 'd', move diagonally to (2,2). At (2,2), s1[1]='b', s2[1]='b' match → take 'b', move diagonally to (1,1), where s1[0]='a' and s2[0]='c' mismatch against zero neighbors, ending the trace. Collected in order 'a', 'd', 'b'; reversed: "bda".

Java (bottom-up, O(min(m,n)) space for length; full table if reconstruction needed)

public int longestCommonSubsequence(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i - 1) == s2.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];
}

Pitfalls

• Off-by-one on the table: dp is (m+1)×(n+1), and s1.charAt(i-1)/s2.charAt(j-1) — mixing up i and i-1 silently shifts every comparison.
• Confusing LCS with longest common substring (which requires contiguity and resets to 0 on mismatch) — different recurrence entirely.
• Reconstructing the actual subsequence requires walking back through the full O(m·n) table; the space-optimized rolling-row version only gives the length, not the sequence.
• For very large inputs (m, n ~ 10^5) O(m·n) is too slow/memory-heavy; that needs Hunt–Szymanski or the Crochemore et al. bit-parallel bit-vector LCS technique, not plain DP.

When to use / when not

Use LCS DP whenever you need order-preserving common structure between two sequences: diff tools, DNA sequence alignment, version-control merge bases, spell-check/autocorrect edit-distance variants. It naturally extends to edit distance (add substitute cost) and shortest common supersequence (m+n-LCS).

vs. Longest Common Substring: use substring DP instead if contiguity is required (e.g., finding a shared literal chunk); its recurrence resets to 0 on mismatch rather than taking a max, giving a different table and answer definition.

vs. Suffix automaton / suffix array: for repeated LCS-style queries across many strings or very large single strings, suffix structures answer in better amortized time at the cost of much higher implementation complexity and O(n) extra space overhead — not worth it for a single one-off comparison of modest strings (n ≤ ~5000).

Not suited when strings are huge (>10^5) and only an approximate or bounded-edit-distance answer is needed — banded DP or hashing-based approximations are cheaper.

Takeaways

• LCS is a 2D DP over index pairs (i, j): match → diagonal +1; mismatch → max of the two neighbors.
• Time is O(m·n) because there are exactly that many distinct subproblems, each O(1) work.
• Space collapses from O(m·n) to O(min(m,n)) if you only need the length, not the traceback.
• Don't confuse with longest common substring — the recurrences differ at the mismatch case.
• Quick sanity checks: two identical strings → LCS = n; strings with no shared characters → 0; "passport" × "ppsspt" → 5 (the chain p·s·s·p·t).

Recall: Why does the space complexity reduce to O(min(m,n)) when only the LCS length is required, and what do you lose by doing so?

Derived from the classic Longest Common Subsequence DP formulation (Cormen et al., Introduction to Algorithms, and standard interview-prep sources).