19 / 75
Medium
Longest Common Subsequence
#19dynamic-programmingstring
Find longest common subsequence between two strings using 2D DP table.
Example:
Input:
text1='abcde', text2='ace'Output:
3 (LCS: 'ace')Common Mistakes:
- Off-by-one errors when accessing strings (use i-1, j-1)
- Forgetting base case (empty string has LCS of 0)
- Not optimizing space to O(n) by using rolling array
Notes:
Classic 2D DP. Time O(m*n), Space O(m*n) or O(min(m,n)) with optimization. Can reconstruct actual subsequence by backtracking.
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Find longest common subsequence between two strings using 2D DP table.
Example:
Input:
text1='abcde', text2='ace'Output:
3 (LCS: 'ace')Common Mistakes:
- Off-by-one errors when accessing strings (use i-1, j-1)
- Forgetting base case (empty string has LCS of 0)
- Not optimizing space to O(n) by using rolling array
Notes:
Classic 2D DP. Time O(m*n), Space O(m*n) or O(min(m,n)) with optimization. Can reconstruct actual subsequence by backtracking.
19/75
Longest Common Subsequence