StringProblem 31 of 43
Find the longest common subsequence between two strings
Problem Statement
Given two strings, find the length of their Longest Common Subsequence (LCS). A subsequence is a sequence that appears in the same relative order but not necessarily contiguous.
Example:
- Input: s1 = "AGGTAB", s2 = "GXTXAYB"
- Output: 4
- Explanation: LCS is "GTAB"
Example 2:
- Input: s1 = "ABCDGH", s2 = "AEDFHR"
- Output: 3
- Explanation: LCS is "ADH"
Approach 1: Brute Force (Recursion)
Intuition
For each character, we have two choices: include it in LCS if it matches, or skip it. Try all possibilities recursively.
Algorithm
- Compare last characters of both strings
- If they match, include in LCS and recurse on remaining
- If they don't match, try skipping from either string
- Take maximum of all possibilities
java
public class Solution {
private int lcsRecursive(String s1, String s2, int i, int j) {
// Base case: if either string is exhausted
if (i == 0 || j == 0) {
return 0;
}
// If characters match, include in LCS
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
return 1 + lcsRecursive(s1, s2, i - 1, j - 1);
}
// Characters don't match, try skipping from either string
return Math.max(lcsRecursive(s1, s2, i - 1, j),
lcsRecursive(s1, s2, i, j - 1));
}
public int longestCommonSubsequence(String s1, String s2) {
return lcsRecursive(s1, s2, s1.length(), s2.length());
}
}Complexity Analysis
- Time Complexity: O(2^(n+m)) - Each call branches into two
- Space Complexity: O(n + m) - Recursion stack depth
Approach 2: Memoization (Top-Down DP)
Intuition
The recursive solution has overlapping subproblems. Cache results to avoid recomputation.
java
import java.util.*;
public class Solution {
private int[][] memo;
private int lcs(String s1, String s2, int i, int j) {
if (i == 0 || j == 0) {
return 0;
}
if (memo[i][j] != -1) {
return memo[i][j];
}
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
memo[i][j] = 1 + lcs(s1, s2, i - 1, j - 1);
} else {
memo[i][j] = Math.max(lcs(s1, s2, i - 1, j), lcs(s1, s2, i, j - 1));
}
return memo[i][j];
}
public int longestCommonSubsequence(String s1, String s2) {
int n = s1.length(), m = s2.length();
memo = new int[n + 1][m + 1];
for (int[] row : memo) Arrays.fill(row, -1);
return lcs(s1, s2, n, m);
}
}Complexity Analysis
- Time Complexity: O(n * m) - Each subproblem solved once
- Space Complexity: O(n * m) - Memo table + recursion stack
Approach 3: Tabulation (Bottom-Up DP) - Optimal
Intuition
Build solution bottom-up using a 2D table. dp[i][j] represents LCS of first i characters of s1 and first j characters of s2.
Algorithm
- Create dp table of size (n+1) x (m+1)
- Initialize first row and column to 0 (empty string cases)
- For each cell dp[i][j]:
- If s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
- Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- Return dp[n][m]
java
public class Solution {
public int longestCommonSubsequence(String s1, String s2) {
int n = s1.length(), m = s2.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s1.charAt(i - 1) == s2.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];
}
}Dry Run Example
s1 = "ABCD", s2 = "AEBD"
"" A E B D
"" 0 0 0 0 0
A 0 1 1 1 1
B 0 1 1 2 2
C 0 1 1 2 2
D 0 1 1 2 3
LCS length = 3 (ABD)
Complexity Analysis
- Time Complexity: O(n * m)
- Space Complexity: O(n * m)
Approach 4: Space Optimized DP
Intuition
We only need the previous row to compute the current row. Reduce space to O(m).
java
public class Solution {
public int longestCommonSubsequence(String s1, String s2) {
int n = s1.length(), m = s2.length();
// Make s2 the shorter string
if (n < m) {
String temp = s1; s1 = s2; s2 = temp;
int t = n; n = m; m = t;
}
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 (s1.charAt(i - 1) == s2.charAt(j - 1)) {
curr[j] = prev[j - 1] + 1;
} else {
curr[j] = Math.max(prev[j], curr[j - 1]);
}
}
int[] temp = prev; prev = curr; curr = temp;
}
return prev[m];
}
}Complexity Analysis
- Time Complexity: O(n * m)
- Space Complexity: O(min(n, m))
Printing the LCS
To print the actual LCS, backtrack through the DP table:
Key Takeaways
- LCS is a classic DP problem - Understand the recurrence relation
- Two choices at each step: match current characters or skip from either string
- Space can be optimized from O(n*m) to O(min(n,m))
- Applications: diff utilities, DNA sequence alignment, version control
- Related problems: Longest Common Substring, Edit Distance, Shortest Common Supersequence
- LCS length helps compute edit distance:
edit_dist = n + m - 2*LCS