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