#1143
Longest Common Subsequence
Medium 2D DP on two strings
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the length of the longest sequence of characters that appears in both strings in the same order (not necessarily contiguous).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the longest sequence of letters in both strings, in order.
Why this works: dp[i][j] for prefixes: equal last letters → 1 + diagonal; otherwise the better of dropping a letter from either string.
Example: "abcde" and "ace"
matches a, c, e → 3✦Hints open one at a time
dp[i][j] = LCS of the first i characters of a and the first j of b.
If a[i−1] == b[j−1], dp[i][j] = dp[i−1][j−1] + 1; otherwise max(dp[i−1][j], dp[i][j−1]).
↗Approach
Fill an (n+1) × (m+1) table row by row; row 0 and column 0 are 0 (empty prefix).
</>Solution (Java)
class Solution {
public int longestCommonSubsequence(String a, String b) {
int n = a.length(), m = b.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a.charAt(i - 1) == b.charAt(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[n][m];
}
}!Common mistake
Confusing subsequence with substring and resetting to 0 on a mismatch.
Complexity
- Time: O(n·m).
- Space: O(n·m), reducible to O(m).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon