Longest Common Subsequence
Longest subsequence (order kept, gaps allowed) present in both strings text1 and text2.
- 1 <= text1.length, text2.length <= 1000
- text1 and text2 consist of only lowercase English characters.
Intuition
The longest common subsequence of two strings is the longest sequence of characters appearing in both, in order but not necessarily adjacent. Enumerating subsequences is exponential — a string of length n has 2ⁿ of them — so the search has to be restructured.
Compare the two strings by prefix pairs instead. Let dp[i][j] be the LCS length of the first i characters of one string and the first j of the other. Now look only at the two characters at those ends, and there are exactly two situations.
If they match, that pair can safely end a common subsequence. Nothing is lost by taking it, so the answer is one more than the LCS of both shorter prefixes — the diagonal cell.
If they differ, at least one of those two characters cannot be part of the LCS ending here. You do not know which, so try both and keep the better:
- On a mismatch, dp[i][j] = max(dp[i−1][j], dp[i][j−1]) — drop a character from one string or the other.
That is the whole recurrence. Every subproblem is a smaller prefix pair, and there are only n × m of them, so the exponential search collapses to a table.
This table is worth knowing cold. Edit distance is the same shape with different costs, diff tools are built on it, and the longest palindromic subsequence is this run against the reversed string.
Two strings, and a question about matching them up while preserving order — that's a 2-D grid DP where dp[i][j] answers the question for the first i and first j characters. The recurrence writes itself from one question: do the current two characters match? If yes, use them and step both back; if not, try dropping one from either side. Edit distance, shortest common supersequence and interleaving-string all fall out of the same frame.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(m·n) time and O(m·n) space.
Define the state over prefix pairs
dp[i][j] is the LCS length of text1[:i] and text2[:j]. Indexing by prefix lengths rather than by subsequences is what turns 2ⁿ possibilities into (n+1) × (m+1) cells.
Set the empty-prefix base cases
dp[i][0] = 0 and dp[0][j] = 0, since an empty string shares nothing with anything. These form the first row and column, and every other cell chains back to them.
Take the diagonal plus one on a match
If the two current characters are equal, they can end a common subsequence, so dp[i][j] = dp[i-1][j-1] + 1. Taking the match is never wrong — it can be proven that some optimal LCS uses it, so no alternative needs exploring.
Take the better of two drops on a mismatch
If they differ, at least one is unusable here. Try discarding each: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Using the diagonal in this case is the common error and undercounts the result.
Fill row by row
Process i outer and j inner so the three cells each entry depends on — up, left, diagonal — are already computed. The answer is dp[m][n], the bottom-right cell.
Collapse to one row when only the length is needed
Each cell reads only the previous row and the cell to its left, so O(min(n, m)) space suffices with one saved diagonal value. Keep the full table only if the actual subsequence must be reconstructed.
Cost of the table
Every one of the n × m cells is computed once in O(1), giving O(n·m) time. Note that LCS and longest common substring are different problems — the substring version requires contiguity and uses a different recurrence.
Solution & live demo
Common pitfalls
Sizing the table m × n instead of (m+1) × (n+1)
dp = [[0] * n for _ in range(m)]
dp = [[0] * (n + 1) for _ in range(m + 1)]
The extra row and column represent empty prefixes, and their zeros are the base case the whole recurrence leans on. Without them dp[i-1][j-1] falls off the grid at the first cell and you need special-cased branches everywhere.
Mixing up table indices and string indices
if text1[i] == text2[j]:
if text1[i-1] == text2[j-1]:
Because row i stands for the first i characters, the character it just added is at string position i - 1. Using i directly compares the wrong pair and runs off the end of the string on the last row.
Adding 1 in the mismatch branch
dp[i][j] = 1 + max(dp[i-1][j], dp[i][j-1])
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
The subsequence only grows when characters actually match. On a mismatch you're discarding one character and inheriting the best answer from a smaller problem — nothing was added to the common subsequence.
Edge cases
Table stays 0 everywhere — answer 0.
Row/column 0 base case handles it.
Diagonal fills 1,2,3,… — answer is the full length.