Given two strings text1 and text2, return the length of their longest common subsequence.
A subsequence of a string is formed by deleting zero or more characters without disturbing the relative order of the remaining characters — the kept characters don't need to be contiguous. A common subsequence of two strings is a subsequence of both. If the two strings share no characters in common order, return 0.
Example
"ace" is a subsequence of both strings, and no longer common subsequence exists.
Constraints
- 1 <= text1.length, text2.length <= 1000
- text1 and text2 consist of lowercase English letters
Intuition
A first pass tries every possible way of building a common subsequence directly: at each pair of positions (i, j), either take the matching characters when text1[i] equals text2[j], or skip a character from one string or the other, trying both and keeping whichever choice leads to the longer result.
function longestCommonSubsequence(text1, text2) {
// solve(i, j) = LCS length of the suffixes text1[i:] and text2[j:].
function solve(i, j) {
// Either suffix ran out — no characters left to match.
if (i === text1.length || j === text2.length) return 0;
if (text1[i] === text2[j]) {
// Characters match: take both and recurse past them in both strings.
return 1 + solve(i + 1, j + 1);
}
// No match: skip a character from either string and keep the better outcome.
return Math.max(solve(i + 1, j), solve(i, j + 1));
}
return solve(0, 0);
}This is O(2^(m+n)) — even though solve(i, j) only depends on the two suffix start positions i and j, the recursion tree re-derives it from scratch every time a different sequence of match/skip choices happens to land on the same pair, and there are only (m + 1) × (n + 1) distinct pairs total. Can we do better?
The key observation: solve(i, j) means the same thing every time it's called — the LCS length of text1[i:] and text2[j:] — so once it's answered it never needs answering again. That's the overlapping-subproblems signature dynamic programming exists to eliminate — the same signature that turns Longest Palindromic Substring's substring re-scans into an O(n²) interval table, and reappears in Edit Distance's two-string alignment table.
Flip the recursion into a table filled bottom-up instead: let dp[i][j] hold exactly what solve(i, j) computed, with an extra zero-filled row and column for the base case where a suffix has run out. Fill it from the bottom-right corner backward — i from m - 1 down to 0, j from n - 1 down to 0 — so that whenever a cell is being computed, the two cells it depends on (one row below, one column to the right) are already sitting in the table. On a match, dp[i][j] = 1 + dp[i+1][j+1] (take the character, move past it in both strings); otherwise dp[i][j] = max(dp[i+1][j], dp[i][j+1]) (skip a character from whichever string, and keep whichever skip did better).
Walking it through:
dp[i][j] = LCS length of text1[i:] and text2[j:], for text1 = "acbcf" (rows) and text2 = "abcf" (cols)
Row 5 (i = m) is the empty suffix of text1; column 4 (j = n) is the empty suffix of text2. An empty suffix shares nothing with anything, so both are seeded to 0 before the fill starts.
The very last characters of both strings match, so the two one-character suffixes share a common subsequence of length 1 — the first real cell in the table.
Row 4 finished filling in (every cell just inherits or extends the one before it). Another match: this 'c' pairs with text2's 'c', extending the earlier 'f' match into 'cf'.
Row 3 is done. 'b' matches too, stitching onto 'cf' to build 'bcf' — three characters long so far.
No match here, so this cell just inherits the better of skipping a character from either string — the max of below (2) and right (3) — without adding a new character to the subsequence.
Row 1 filled in the same way in between (dp[1][1] = 3, inherited from dp[2][1] since 'c' ≠ 'b' there too). The first characters match, giving the final answer: dp[0][0] = 4, the length of "abcf".
Optimization
Bottom-up 2-D DP
Let dp[i][j] be the LCS length of the suffixes text1[i:] and text2[j:]. Filling from the ends backward: if the characters at i and j match, they can both be part of the LCS, so dp[i][j] = 1 + dp[i+1][j+1]; otherwise the LCS skips one character from either string, so dp[i][j] = max(dp[i+1][j], dp[i][j+1]). The answer is dp[0][0], and the base case dp[m][*] = dp[*][n] = 0 handles either string running out.
O(m * n) time, O(m * n) space.
function longestCommonSubsequence(text1, text2) {
const m = text1.length;
const n = text2.length;
// dp[i][j] = LCS length of text1[i:] and text2[j:]; extra row/col of zeros for the empty-suffix base case
// (dp[m][*] and dp[*][n] never get overwritten below, so they stay 0).
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
// Fill from the bottom-right corner backward, so dp[i+1][j+1], dp[i+1][j], and dp[i][j+1] are
// always already computed by the time dp[i][j] needs them.
for (let i = m - 1; i >= 0; i--) {
for (let j = n - 1; j >= 0; j--) {
if (text1[i] === text2[j]) {
// Characters match: take both and extend the LCS found for the suffixes past this pair.
dp[i][j] = 1 + dp[i + 1][j + 1];
} else {
// No match: skip a character from either string and keep whichever skip did better.
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j + 1]);
}
}
}
// dp[0][0] is the LCS length of the two full strings.
return dp[0][0];
}Complexity analysis
Time complexity: O(m·n). Here's why:
- The fill computes exactly one value per cell of the
(m + 1) × (n + 1)dp table. - Each cell does O(1) work — one character comparison, then either an addition or a
maxover two already-known neighbors.
So the whole fill costs (m + 1)(n + 1) × O(1) = O(m·n) — down from the brute force's exponential O(2^(m+n)), since every (i, j) pair is now computed exactly once instead of re-derived by every match/skip path that reaches it.
Space complexity: O(m·n). Here's why:
- The stored solution keeps the full
(m + 1) × (n + 1)dp table, sincedp[i][j]readsdp[i+1][j]anddp[i][j+1]— the row below and this row's later columns. - There's no recursion, so no call stack to add on top — unlike the brute force's O(m+n)-deep call stack.
The two input strings aren't counted as extra space — only what the algorithm allocates beyond them. That table costs O(m·n); it could be rolled down to O(n) by keeping only the row below, the way Unique Paths rolls its table — though here a match reads the diagonal cell dp[i+1][j+1], which gets overwritten as soon as the current row starts filling in, so the fold needs one extra saved value to hold it, not just a plain running sum.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| text1 = "", text2 = "xyz" | 0 | One string empty — no characters exist to match, so the LCS is empty regardless of the other string. |
| text1 = "k", text2 = "k" | 1 | Single matching character in both strings — the LCS is that one character. |
| text1 = "p", text2 = "q" | 0 | Two single, distinct characters — the smallest case with no common subsequence at all. |
| text1 = "zzz", text2 = "zz" | 2 | Both strings are runs of the same character — the LCS length is capped by the shorter string's length (2), not the total number of occurrences. |
| text1 = "abab", text2 = "baba" | 3 | Alternating repeated characters in both strings — several equally long common subsequences exist ('aba' or 'bab'), and the DP only needs the length, not which one. |
Try it yourself
Write your solution against the real judge before checking the reference.