Learning Outcome
After this lesson, you should be able to define a DP state over two prefixes and reduce memory to two rows.
Problem Statement
Given two strings, return the length of their longest common subsequence.
| Input | Output | Why |
|---|---|---|
text1 = "abcde", text2 = "ace" | 3 | The common subsequence "ace" has length 3. |
Brute Force Approach
Generate every subsequence of both strings and compare them. This is exponential.
Optimized Approach
Use DP over prefixes. If characters match, extend the diagonal state; otherwise take the best from skipping one character.
Exact Pseudocode
prev = array of zeros with length n + 1
for i from 1 to length(text1):
curr = array of zeros
for j from 1 to length(text2):
if text1[i - 1] == text2[j - 1]:
curr[j] = prev[j - 1] + 1
else:
curr[j] = max(prev[j], curr[j - 1])
prev = curr
return prev[n]Reference Code
class Solution:
def longestCommonSubsequence(self, text1, text2):
n = len(text2)
prev = [0] * (n + 1)
for a in text1:
curr = [0] * (n + 1)
for j, b in enumerate(text2, 1):
if a == b:
curr[j] = prev[j - 1] + 1
else:
curr[j] = max(prev[j], curr[j - 1])
prev = curr
return prev[n]Sample Dry Run
| Step | State | Result |
|---|---|---|
| a vs ace | match a | best length becomes 1 |
| b row | no useful match | best stays 1 |
| c row | match c after a | best becomes 2 |
| e row | match e after ac | answer = 3 |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(m * n) | Every pair of prefix positions is evaluated once. |
| Space | O(n) | Two rows store the previous and current prefix states. |
Edge Cases
- If either string is empty, the answer is 0.
- Subsequence does not require contiguous characters.
- Do not confuse this with longest common substring.
Interview Checklist
- Use diagonal + 1 when characters match.
- Use max of top and left when they do not match.
- Keep row order consistent when optimizing space.
FAQs
Why does matching use the diagonal?
A match extends the best answer from both prefixes before these two characters.
Why not use one string only?
The state depends on positions in both strings, so two dimensions are needed conceptually.
What is the core pattern?
Two-string prefix DP.