~20 minutes · Day 68 · 2D dynamic programming
Tonight's interview shape is two strings and one question: how much order do they share? Longest Common Subsequence asks for the length of the longest sequence that appears in both strings without changing order. A subsequence may skip characters; it does not have to be contiguous (Wikipedia: longest common subsequence).
When characters match, extend the diagonal:
dp[i][j] = dp[i-1][j-1] + 1; otherwise take the better of dropping one character from either string.
That's the whole grid. Every cell answers a smaller version of the same question: “what is the LCS length for these two prefixes?”
One brute force idea is to generate every subsequence of text1, then check whether each one appears as a subsequence of text2. That is O(2m · n) time in the usual two-string case, because one string has exponentially many subsequences and each check can scan the other string. It works as a thought experiment, but it is too slow for interviews.
The repeated work is the clue. The same prefix pairs show up again and again. Dynamic programming keeps one answer per prefix pair, so each state is computed once.
Define dp[i][j] as the LCS length between text1[:i] and text2[:j]. Row 0 and column 0 are zero: an empty string shares nothing with anything. Then fill left-to-right, top-to-bottom.
Now the code is just the diagram written carefully:
def longestCommonSubsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)] # empty prefix row/col
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]: # last chars match
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n] # full text1 vs full text2
The index shift is normal: dp[i][j] talks about prefix lengths, while text1[i - 1] and text2[j - 1] are the last characters inside those prefixes.
Edit Distance also puts one string on rows and the other on columns. Before revealing: what are the four DP questions here - state, transition, base case, answer location?
The state is still dp[i][j] for two prefixes. The base row and column mean turning a prefix into an empty string. The answer still lives at dp[m][n]. The transition changes: if characters match, take the diagonal unchanged; otherwise choose the cheapest insert, delete, or replace from neighboring states. Same two-string grid, different cell rule.
| Approach | Time | Space |
|---|---|---|
| Brute force (try subsequences) | O(2m · n) | O(m) |
| 2D DP (one cell per prefix pair) | O(mn) | O(mn) |
Here m = len(text1) and n = len(text2). A full table is the clearest first version; later, the same recurrence can be compressed because each row only needs the row above and the current row's left cell.
1. What does dp[i][j] mean in this lesson?
dp[i][j] stores the length of the longest common subsequence between the first i characters of text1 and the first j characters of text2.2. When the two current characters match, what happens?
3. Spot the bug in this loop:
for i in range(1, len(text1) + 1):
for j in range(1, len(text2) + 1):
if text1[i] == text2[j]:
dp[i][j] = dp[i - 1][j - 1] + 1text1[i - 1] and text2[j - 1]. Using i and j skips the first character and can run off the end.4. Which task asks for this pattern?
Solve Longest Common Subsequence using the cycle - predict → attempt → compare → encode - in your Notion tracker.
dp[i][j], the base row/column, the match rule, and the mismatch rule before coding.Watch NeetCode - Longest Common Subsequence after your attempt, as the compare step. Look for the moment where the diagonal move becomes obvious.
Stuck or curious? Ask your teacher (the agent) - that's what it's for.