March 24
Longest Common Subsequence
How to turn comparison between two strings into a table of subproblems instead of repeating recursion choices.
Dynamic Programming Intermediate 25 min TypeScript
Given two strings text1 and text2, return the length of their longest common subsequence.
If there is no common subsequence, return 0.
Example:
Input: text1 = "abcde", text2 = "ace"
Output: 3
The longest common subsequence is "ace", with length 3.
What to notice before coding
- A subsequence does not need to be contiguous.
- The answer is a length, so you do not need to reconstruct the string here.
- When the characters do not match, the decision becomes "which side is worth skipping now?".
Common mistakes
- mixing up subsequence with substring
- getting the table state wrong and then losing track of the indexes
Step 1 - Do not mix subsequence with substring
Here you are allowed to skip characters.
That means "ace" is a subsequence of "abcde" even though it is not glued together.
If you think in substring terms, you will build the wrong solution.
Step 2 - Write the recursive baseline
The natural baseline is:
- look at the current character on both sides
- if they match, count 1 and move both
- if they do not match, try skipping one side or the other
It works.
But it repeats many subproblems.
Step 3 - Define the right state
A good definition is:
dp[i][j]= best answer using the firsticharacters oftext1and the firstjcharacters oftext2
This helps because each cell depends on smaller, well-defined subproblems.
Step 4 - Find the transition
If the last characters match:
dp[i][j] = dp[i - 1][j - 1] + 1
If they do not:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
That is the central table rule.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function longestCommonSubsequence(text1: string, text2: string): number {
// your solution here
return 0
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(m * n)
Space: O(m * n)
Solution 1 - Pure recursion
Good baseline because it makes the choice logic visible.
export function longestCommonSubsequence(text1: string, text2: string): number {
function dfs(index1: number, index2: number): number {
if (index1 === text1.length || index2 === text2.length) {
return 0
}
if (text1[index1] === text2[index2]) {
return 1 + dfs(index1 + 1, index2 + 1)
}
return Math.max(dfs(index1 + 1, index2), dfs(index1, index2 + 1))
}
return dfs(0, 0)
}It works, but it explodes in repeated work.
The intermediate step would be memoization: cache each (index1, index2) pair so the same subproblem is not solved again.
Solution 2 - 2D dynamic programming
Now each subproblem is solved once.
export function longestCommonSubsequence(text1: string, text2: string): number {
const rows = text1.length + 1
const cols = text2.length + 1
const dp = Array.from({ length: rows }, () => new Array(cols).fill(0))
for (let i = 1; i < rows; i += 1) {
for (let j = 1; j < cols; j += 1) {
if (text1[i - 1] === text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
}
}
}
return dp[text1.length][text2.length]
}The strong insight here is noticing that recursion was already giving you the formula. Dynamic programming only organizes it into a table.
What to say in the interview
A strong short explanation would be:
The recursive baseline compares the current characters. If they match, I count 1 and move both. If they do not, I try skipping one side or the other. The problem is repeated work. So I turn that into 2D DP, where
dp[i][j]stores the best answer for the firstiandjcharacters.
That shows that you:
- clearly separated subsequence from substring
- connected recursion to the table
- explained the transition without memorized formulas floating around
When this pattern shows up again
This pattern comes back when you need to:
- compare two sequences at the same time
- fill a 2D table of subproblems
- translate recursion choices into iterative dynamic programming
The point is not memorizing
Longest Common Subsequence.
The point is learning how to model two-dimensional subproblems.