Longest Common Subsequence
The Longest Common Subsequence (LCS) problem finds the longest subsequence common to two strings. It is solved with DP in O(m*n) time.
Recurrence: if characters match, dp[i][j] = 1 + dp[i-1][j-1]; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Java implementation:
public static int lcs(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[][] dp = new int[m+1][n+1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i-1) == s2.charAt(j-1)) {
dp[i][j] = 1 + dp[i-1][j-1];
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[m][n];
}
LCS is used in diff tools, bioinformatics, and version control.
Two Minute Drill
- LCS finds longest common subsequence (not necessarily contiguous).
- Time O(mn), space O(mn) (can be optimized to O(min(m,n))).
- Base case: dp[0][j] = dp[i][0] = 0.
- Recurrence based on character equality.
Need more clarification?
Drop us an email at career@quipoinfotech.com