Longest Common Subsequence

Difficulty: Hard

Problem

The canonical TWO-STRING DP. Given two strings, return the length of their longest common subsequence: the longest run of characters that shows up in BOTH strings in the same order, with gaps 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 = "programming", text2 = "gaming"
Output: 6
Explanation: "gaming" is itself a subsequence of "programming" (g, a, m, i, n, g appear in that order), so the answer equals the length of "gaming", 6, and nothing can be longer.

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

Pseudocode

function longestCommonSubsequence(t1, t2):
    m = length(t1), n = length(t2)
    # dp[i][j] = LCS of t1's first i chars vs t2's first j
    dp = (m+1) x (n+1) table, every cell = ____
    
    for i from 1 to m:
        for j from 1 to n:
            if t1[i-1] == t2[j-1]:
                dp[i][j] = ____ + 1
            else:
                dp[i][j] = max(____, ____)
    
    return ____

Hints

  • What does an EMPTY prefix share with anything? That one value is the correct base for the whole first row and column, the initializer can pre-pay it.
  • Match: pair the two last characters and retreat BOTH prefixes one step. Which cell holds that smaller answer? (It's the diagonal.)
  • Mismatch: at least one last character is dead weight. Drop t1's last (the cell ABOVE) or t2's last (the cell to the LEFT). Keep the better of the two.
  • The state sentence says dp[i][j] covers the first i and first j characters, so the FULL-strings answer lives in which cell?

Complexity questions

The naive recursion branches on every mismatch. How bad is it, and how many DISTINCT subproblems actually exist?

Roughly O(2^(m+n)) calls, yet only (m+1)×(n+1) distinct (i, j) prefix pairs, the classic cache-collision setup. Each mismatch spawns two calls whose subtrees re-meet at (i−1, j−1), so the tree doubles level after level. But i and j each only shrink, so the distinct questions number just (m+1)×(n+1). An exponential tree chasing a polynomial state space is DP's favorite meal.

The tabulated solution's time complexity?

O(m·n): one constant-time fill (a compare, then diagonal+1 or a max) per cell of the (m+1)×(n+1) table. Two nested loops visit each of the (m+1)×(n+1) cells exactly once, and each fill reads at most three already-final neighbors, constant work. Total: O(m·n) time, O(m·n) space for the full table.

The transition reads dp[i−1][j−1], dp[i−1][j], and dp[i][j−1]. Why can space drop to O(n), and what's the trap?

Only row i−1 and the current row are ever read → two rows suffice; a single row also works IF you stash the old dp[j−1] in a variable before overwriting it, because the diagonal needs that OLD value. The reach is one row back, so two rows suffice: the space-optimization rule from the foundations. The one-row version has a trap: filling left to right, dp[j−1] already holds the NEW row's value when you need the diagonal, so the OLD value must be saved in a temp variable before each write. O(1) is impossible: a whole row of history feeds the next row.

Edit distance (minimum inserts/deletes/replaces to turn one string into the other) uses the very same (m+1)×(n+1) prefix-pair table. What changes?

Only the transition: the same three neighbors (up, left, diagonal) combine as 1 + min(...) for delete/insert/replace, with a free diagonal on a match. Same state, same edge bases (now i and j), same row-by-row fill. Same discipline, different combiner: mismatched cells take 1 + min(up, left, diagonal) (delete text1's last, insert text2's last, or replace one with the other) and the edges become i and j (emptying a prefix costs one edit per character). Master this table once and a whole family of string problems falls.

Check your understanding of Longest Common Subsequence

First, vocabulary: a COMMON SUBSEQUENCE of two strings is...?

Characters picked IN ORDER from each string, skips allowed, spelling the same sequence in both, 'ace' is one for 'abcde' and 'ace'. Order preserved, gaps allowed: that's a subsequence, and a COMMON one must thread through both strings. 'ace' walks through 'abcde' by skipping b and d. Substrings demand contiguity (a different classic), and rearranging letters is never allowed.

Why is the state 2D here. What exactly does dp[i][j] mean?

TWO prefixes advance independently, so the state is a pair: dp[i][j] = the LCS length of text1's first i characters and text2's first j characters. Straight from the foundations: two movers → two indexes. How much of text1 is consumed and how much of text2 are independent facts, so one index can't describe a subproblem. The subproblem is a PAIR of prefixes, dp[i][j] = LCS of text1[:i] vs text2[:j].

The MATCH rule: text1[i−1] == text2[j−1]. The last characters of both prefixes are equal. What is dp[i][j]?

dp[i−1][j−1] + 1: pair the matched characters and retreat BOTH prefixes one step: the diagonal, plus one. Pair the two matching last characters (+1) and both prefixes shrink by one. That smaller subproblem is the DIAGONAL neighbor dp[i−1][j−1]. Pairing is always safe: any best answer that skipped this pair could swap its own final match for this one at no cost in length.

And the MISMATCH rule: the last characters differ. dp[i][j] = ?

max(dp[i−1][j], dp[i][j−1]), at least one of the two last characters is dead weight, so try dropping each and keep the better. Two DIFFERENT characters can't both end the common subsequence, so at least one contributes nothing. You can't know which, so try both retreats: drop text1's last (up, dp[i−1][j]) or drop text2's last (left, dp[i][j−1]), and keep the max.

Base cases: which states are known for free?

The entire first row and first column are 0: an empty prefix shares nothing with anything. If either prefix is empty (i = 0 or j = 0), there is no common subsequence, length 0. The bases live on the table's EDGES, exactly like Unique Paths, and a zero-initialized table pre-pays every one of them.

Related problems

Keep practising