Longest Common Subsequence

Difficulty: Hard

Problem

The canonical TWO-STRING DP. Given two strings, return the length of their longest common subsequence. The longest sequence of characters that appears in BOTH strings in order, skips allowed. You've filled grids with dp[r][c]; today the two dimensions are PREFIXES of two different strings, and the table you build is the one behind git diff, spell checkers, and DNA alignment.

Example

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: "ace" appears in "abcde" as a subsequence (take a, skip b, take c, skip d, take e) and is all of "ace". Shared by both, length 3, and nothing longer is.

Brute-force approach

The naive two-prefix recursion is Step 1 of the guided arc below. Watch it explode into overlapping calls, then cure it with the pair-keyed notebook and the table.

Optimal approach

Key insight: Look at the LAST characters of both prefixes. Match? Pair them and shrink both (diagonal + 1). Mismatch? One is useless. Drop each in turn and keep the better (max of up/left).

The full arc on the canonical two-string DP: case-split on the LAST characters of both prefixes (naive recursion), memoize with a pair key, then tabulate an (m+1)×(n+1) table row by row. The answer waits in the bottom-right corner.

Steps

  1. State sentence: dp[i][j] = the LCS length of text1's first i characters and text2's first j characters
  2. Bases: first row and first column are 0, an empty prefix shares nothing
  3. Match (text1[i−1] == text2[j−1]): dp[i][j] = dp[i−1][j−1] + 1, the diagonal, plus the pair
  4. Mismatch: dp[i][j] = max(dp[i−1][j], dp[i][j−1]). Drop one last character, keep the better
  5. Fill row by row, left to right; the answer is dp[m][n] in the bottom-right corner

Time complexity: O(m × n) · Space complexity: O(n) with a rolling row