Approach Summary
dp[i][j] = LCS of first i chars of s1 and first j chars of s2. If match: dp[i-1][j-1]+1. Else: max(dp[i-1][j], dp[i][j-1]).
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Top-Down Recursion with Memoization | O(m * n) | O(m * n) memo + recursion stack | Explore matching characters recursively with a 2D memoization cache. |
| 2 Approach 2: Space-Optimized Dynamic Programming (Optimal) | O(m * n) | O(min(m, n)) | Maintain two 1D rows (prev and curr) to compute LCS in O(min(m, n)) space. |
Step 1: Baseline
Approach 1: Top-Down Recursion with Memoization
Time: O(m * n)
Space: O(m * n) memo + recursion stack
Define solve(i, j) comparing prefixes of length i and j. If text1[i-1] == text2[j-1], return 1 + solve(i-1, j-1). Otherwise return max(solve(i, j-1), solve(i-1, j)). Store answers in a 2D table initialized with -1 to avoid duplicate computations.
Approach 1: Top-Down Recursion with Memoization Implementation
Approach 1: Top-Down Recursion with Memoization
class Solution {
public int solve(int[][] dp, String text1, String text2, int n, int m) {
if (n == 0 || m == 0) return 0;
if (dp[n][m] != -1) return dp[n][m];
if (text1.charAt(n - 1) == text2.charAt(m - 1)) {
dp[n][m] = 1 + solve(dp, text1, text2, n - 1, m - 1);
} else {
dp[n][m] = Math.max(solve(dp, text1, text2, n, m - 1), solve(dp, text1, text2, n - 1, m));
}
return dp[n][m];
}
public int longestCommonSubsequence(String text1, String text2) {
int n = text1.length();
int m = text2.length();
int[][] dp = new int[n + 1][m + 1];
for (int[] row : dp) Arrays.fill(row, -1);
return solve(dp, text1, text2, n, m);
}
}class Solution {
public:
int solve(vector<vector<int>>& dp, string& text1, string& text2, int n, int m) {
if (n == 0 || m == 0) return 0;
if (dp[n][m] != -1) return dp[n][m];
if (text1[n - 1] == text2[m - 1]) {
dp[n][m] = 1 + solve(dp, text1, text2, n - 1, m - 1);
} else {
dp[n][m] = max(solve(dp, text1, text2, n, m - 1), solve(dp, text1, text2, n - 1, m));
}
return dp[n][m];
}
int longestCommonSubsequence(string text1, string text2) {
int n = text1.size();
int m = text2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));
return solve(dp, text1, text2, n, m);
}
};class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
n, m = len(text1), len(text2)
memo = [[-1] * (m + 1) for _ in range(n + 1)]
def solve(i, j):
if i == 0 or j == 0:
return 0
if memo[i][j] != -1:
return memo[i][j]
if text1[i - 1] == text2[j - 1]:
memo[i][j] = 1 + solve(i - 1, j - 1)
else:
memo[i][j] = max(solve(i, j - 1), solve(i - 1, j))
return memo[i][j]
return solve(n, m)function longestCommonSubsequence(text1, text2) {
const n = text1.length;
const m = text2.length;
const memo = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(-1));
function solve(i, j) {
if (i === 0 || j === 0) return 0;
if (memo[i][j] !== -1) return memo[i][j];
if (text1[i - 1] === text2[j - 1]) {
memo[i][j] = 1 + solve(i - 1, j - 1);
} else {
memo[i][j] = Math.max(solve(i, j - 1), solve(i - 1, j));
}
return memo[i][j];
}
return solve(n, m);
} Step 2: Most Optimized
Approach 2: Space-Optimized Dynamic Programming (Optimal)
Time: O(m * n)
Space: O(min(m, n))
Because dp[i][j] depends solely on values from the previous row (prev[j - 1], prev[j]) and the current row (curr[j - 1]), we can discard rows older than i - 1. Keeping only two rows reduces memory consumption from megabytes to negligible kilobytes.
Approach 2: Space-Optimized Dynamic Programming (Optimal) Implementation
Approach 2: Space-Optimized Dynamic Programming (Optimal)
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int n = text1.length();
int m = text2.length();
int[] prev = new int[m + 1];
int[] curr = new int[m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
curr[j] = 1 + prev[j - 1];
} else {
curr[j] = Math.max(curr[j - 1], prev[j]);
}
}
prev = curr.clone();
}
return prev[m];
}
}class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n = text1.size();
int m = text2.size();
vector<int> prev(m + 1, 0);
vector<int> curr(m + 1, 0);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (text1[i - 1] == text2[j - 1]) {
curr[j] = 1 + prev[j - 1];
} else {
curr[j] = max(curr[j - 1], prev[j]);
}
}
prev = curr;
}
return prev[m];
}
};class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
n, m = len(text1), len(text2)
prev = [0] * (m + 1)
curr = [0] * (m + 1)
for i in range(1, n + 1):
for j in range(1, m + 1):
if text1[i - 1] == text2[j - 1]:
curr[j] = 1 + prev[j - 1]
else:
curr[j] = max(curr[j - 1], prev[j])
prev = list(curr)
return prev[m]function longestCommonSubsequence(text1, text2) {
const n = text1.length;
const m = text2.length;
let prev = new Array(m + 1).fill(0);
let curr = new Array(m + 1).fill(0);
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
if (text1[i - 1] === text2[j - 1]) {
curr[j] = 1 + prev[j - 1];
} else {
curr[j] = Math.max(curr[j - 1], prev[j]);
}
}
prev = [...curr];
}
return prev[m];
}Edge Cases to Watch
- No common characters (e.g. "abc" and "def"; returns 0)
- Identical strings (returns string length)
- One string is an exact subsequence of the other (e.g. "abc" and "aebdc"; returns 3)
- Strings with unequal lengths (e.g. length 1 vs 1000)
Algorithmic Pattern
View Pattern Guide →
Master the Dynamic Programming Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Dynamic Programming pattern.
Framework: Dynamic Programming • Interview Prep: Tested at FAANG •
Explore all Dynamic Programming problems & invariants →
How to Recognize This Pattern
- LCS of two sequences
- 2D DP table
Complexity Analysis
Time Complexity
O(m × n)
Space Complexity
O(m × n)
Tags
String DP
Frequently Asked Questions
What is the optimal time and space complexity for Longest Common Subsequence?
The optimal solution for Longest Common Subsequence achieves O(m × n) runtime complexity and requires O(m × n) auxiliary space. Time complexity is O(m * n) where m and n are string lengths because every cell in the m x n grid is evaluated in O(1) time. Space complexity is O(n) using rolling 1D arrays.
How do I identify that Longest Common Subsequence requires the Dynamic Programming pattern?
In technical interviews, look for key problem signals: LCS of two sequences; 2D DP table. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Dynamic Programming strategy.
What critical edge cases must be handled in Longest Common Subsequence?
Essential edge cases to verify include: No common characters (e.g. "abc" and "def"; returns 0); Identical strings (returns string length); One string is an exact subsequence of the other (e.g. "abc" and "aebdc"; returns 3); Strings with unequal lengths (e.g. length 1 vs 1000). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Longest Common Subsequence?
Longest Common Subsequence is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Google, Amazon, Bloomberg.