Longest Common Subsequence
Find the length of the longest common subsequence of two strings with a 2D DP table: extend the diagonal on a match, otherwise take the better of up and left.
Problem Understanding
Longest Common Subsequence: given two strings text1 and text2, return the length of their longest common subsequence, a sequence of letters that appears in both in the same order (not necessarily contiguous), or 0 if there is none.
Example: text1 = "abcde", text2 = "ace" returns 3; the LCS is "ace".
The Intuition: Compare the Last Letters
Look at the last letters of two prefixes, text1[..i] and text2[..j]:
- They match: that letter can end the common subsequence, so the answer is the LCS of both prefixes without it, plus 1. That is the diagonal,
dp[i − 1][j − 1] + 1. - They differ: at least one of them is not in the LCS. Try dropping each and keep the better:
max(dp[i − 1][j], dp[i][j − 1]).
Empty prefixes share nothing, so row 0 and column 0 are 0. Filling the table row by row is classic 2D dynamic programming, the same grid shape as Unique Paths. The same table, with different costs, solves Edit Distance.
Interactive Walkthrough
text2 runs across the top and text1 down the side, each starting with an empty prefix ∅. Watch each cell take its value from the diagonal (match) or from up/left (no match). At the end, the matches on one longest common subsequence turn green.
Dry Run Table
Input: text1 = "abcde", text2 = "ace"
| ∅ | a | c | e | |
|---|---|---|---|---|
| ∅ | 0 | 0 | 0 | 0 |
| a | 0 | 1 | 1 | 1 |
| b | 0 | 1 | 1 | 1 |
| c | 0 | 1 | 2 | 2 |
| d | 0 | 1 | 2 | 2 |
| e | 0 | 1 | 2 | 3 |
Bold cells are matches. Answer: 3 ("ace").
The Solution Template
A full (m + 1) × (n + 1) table. The C version stores it in one heap block, since a 1001 × 1001 stack array is too big.
Longest Common Subsequence Code
1var longestCommonSubsequence = function(text1, text2) {2 const m = text1.length, n = text2.length;3 const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));4 for (let i = 1; i <= m; i++) {5 for (let j = 1; j <= n; j++) {6 if (text1[i - 1] === text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;7 else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);8 }9 }10 return dp[m][n];11};
Edge Cases & Common Mistakes
- No common letter: every cell stays 0; return 0.
- Off-by-one indexing:
dp[i][j]describes prefixes of length i and j, so comparetext1[i − 1]withtext2[j − 1]. - Adding 1 on a mismatch: only a match extends the diagonal; a mismatch copies the best neighbour.
- Confusing it with longest common substring: substrings must be contiguous, so a mismatch resets to 0 there.
- Recursion without memo: the plain recursion is O(2^(m+n)); cache by (i, j) or fill the table bottom-up.
Summary
dp[i][j] is the LCS length of the first i letters of text1 and the first j of text2. On a match take the diagonal plus 1; otherwise take the larger of up and left. Row 0 and column 0 are 0, and the answer is dp[m][n]. O(m · n) time and space, or O(min(m, n)) space with rolling rows.
More practice: DSA interview questions with answers · patterns cheat sheet