Longest Common Subsequence

The problem. Given two strings text1 and text2, return the length of their longest common subsequence — the longest string you can get from both by deleting letters without reordering the rest. If they share no letters, return 0.

Example

text1 = "abcde",  text2 = "ace"   ->  3   ("ace")
text1 = "abc",    text2 = "abc"   ->  3   ("abc")
text1 = "abc",    text2 = "def"   ->  0

The pattern: two sequences, one table

With two sequences, the state becomes a pair of prefixes. As in every DP, answer four questions. State — what does a cell mean? Here dp[i][j] is the answer for the first i letters of one string and the first j of the other. Transition — how does a cell follow from smaller ones? Usually by looking at the last letters of the two prefixes. Base case — an empty prefix: row 0 and column 0. Answer — the cell for both whole strings, dp[n][m]. Two strings give an (n + 1) × (m + 1) table and O(n · m) time; one string cut into pieces gives a single row, dp[i] for the first i letters.

The idea: compare the last letters

Take the first i letters of text1 and the first j of text2. If their last letters are equal, the LCS can end with that letter: use it, and add one to the answer for both prefixes without it, dp[i-1][j-1]. If they differ, at least one of the two letters is not in the LCS — so drop one or the other and keep the better answer, max(dp[i-1][j], dp[i][j-1]).

1. Plain recursion

1function longestCommonSubsequence(text1, text2) {2  const lcs = (i, j) => {                       // LCS of text1[i..] and text2[j..]3    if (i === text1.length || j === text2.length) return 0;4    if (text1[i] === text2[j]) return 1 + lcs(i + 1, j + 1);5    return Math.max(lcs(i + 1, j), lcs(i, j + 1));   // skip a letter of one string or the other6  };7  return lcs(0, 0);8}

Time O(2ⁿ⁺ᵐ), space O(n + m) for the call stack. Every mismatch branches in two, and the same (i, j) pairs are solved over and over. But there are only (n + 1) × (m + 1) different pairs, so remember each answer.

2. Memoize (i, j)

1function longestCommonSubsequence(text1, text2) {2  const memo = new Map();                       // "i,j" -> LCS of text1[i..] and text2[j..]3  const lcs = (i, j) => {4    if (i === text1.length || j === text2.length) return 0;5    const key = i + "," + j;6    if (memo.has(key)) return memo.get(key);7    const best = text1[i] === text2[j] ? 1 + lcs(i + 1, j + 1) : Math.max(lcs(i + 1, j), lcs(i, j + 1));8    memo.set(key, best);9    return best;10  };11  return lcs(0, 0);12}

Time O(n · m), space O(n · m) for the memo, plus O(n + m) for the call stack. That stack is the catch: LeetCode allows 1,000 letters per string, so the recursion can go 2,000 calls deep — past Python's default limit of 1,000. The table below has no recursion at all.

3. Bottom-up table

1function longestCommonSubsequence(text1, text2) {2  const n = text1.length, m = text2.length;3  // dp[i][j]: the LCS length of text1[0..i) and text2[0..j)4  const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));5  for (let i = 1; i <= n; i++) {6    for (let j = 1; j <= m; j++) {7      if (text1[i - 1] === text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;   // both letters join the LCS8      else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);              // drop one letter or the other9    }10  }11  return dp[n][m];12}

Time O(n · m), space O(n · m). Each cell is filled once from three neighbours that are already done. To recover the subsequence itself, walk back from the bottom-right cell: a diagonal step on matching letters is part of the LCS; otherwise move towards the larger neighbour.

4. Two rows

Each row only reads the row above it, so two rows are enough — and putting the shorter string along them keeps them short.

1function longestCommonSubsequence(text1, text2) {2  if (text2.length > text1.length) [text1, text2] = [text2, text1];   // keep the rows short3  const m = text2.length;4  let prev = new Array(m + 1).fill(0);5  for (let i = 1; i <= text1.length; i++) {6    const cur = new Array(m + 1).fill(0);7    for (let j = 1; j <= m; j++) {8      cur[j] = text1[i - 1] === text2[j - 1] ? prev[j - 1] + 1 : Math.max(prev[j], cur[j - 1]);9    }10    prev = cur;                                 // only the row above is ever needed11  }12  return prev[m];13}

Time O(n · m), space O(min(n, m)). The trade-off: with only two rows kept, the walk back to recover the subsequence is no longer possible.

Comparing the approaches

The table is the answer to give first — it's easy to explain and to trace by hand. Mention the two-row version when asked about memory.

Edge cases to test

Variations