WikiGalaxy
Introduction to Longest Common Subsequence (LCS)
The Longest Common Subsequence (LCS) problem is a classic computer science problem that involves finding the longest subsequence common to two sequences. Unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences.
Example 1: Basic LCS Calculation
Problem Statement:
Given two strings, "ABCBDAB" and "BDCAB", find their longest common subsequence.
Solution Explanation:
The longest common subsequence is "BCAB". This can be found by using dynamic programming to build a table that tracks the lengths of common subsequences.
int lcs(String X, String Y, int m, int n) {
int[][] L = new int[m+1][n+1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X.charAt(i-1) == Y.charAt(j-1))
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = Math.max(L[i-1][j], L[i][j-1]);
}
}
return L[m][n];
}
Console Output:
Length of LCS: 4
Example 2: LCS with Recursive Approach
Problem Statement:
Find the longest common subsequence for strings "AGGTAB" and "GXTXAYB" using a recursive approach.
Solution Explanation:
The LCS is "GTAB". Recursive solutions are intuitive but not efficient for large inputs due to overlapping subproblems.
int lcsRecursive(char[] X, char[] Y, int m, int n) {
if (m == 0 || n == 0)
return 0;
if (X[m-1] == Y[n-1])
return 1 + lcsRecursive(X, Y, m-1, n-1);
else
return Math.max(lcsRecursive(X, Y, m, n-1), lcsRecursive(X, Y, m-1, n));
}
Console Output:
Length of LCS: 4
Example 3: LCS with Space Optimization
Problem Statement:
Optimize the space complexity of the LCS problem for strings "ABCDEF" and "AEBDF".
Solution Explanation:
The LCS is "ABDF". By using only two arrays of size n, we reduce the space complexity from O(m*n) to O(n).
int lcsOptimized(String X, String Y) {
int m = X.length(), n = Y.length();
int[] prev = new int[n+1];
int[] curr = new int[n+1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (X.charAt(i-1) == Y.charAt(j-1))
curr[j] = prev[j-1] + 1;
else
curr[j] = Math.max(prev[j], curr[j-1]);
}
System.arraycopy(curr, 0, prev, 0, n+1);
}
return prev[n];
}
Console Output:
Length of LCS: 4
Example 4: LCS with Backtracking
Problem Statement:
Find the actual LCS sequence for "XMJYAUZ" and "MZJAWXU".
Solution Explanation:
The LCS is "MJAU". We use backtracking on the DP table to construct the sequence.
String lcsBacktrack(String X, String Y) {
int m = X.length(), n = Y.length();
int[][] L = new int[m+1][n+1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X.charAt(i-1) == Y.charAt(j-1))
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = Math.max(L[i-1][j], L[i][j-1]);
}
}
int index = L[m][n];
char[] lcs = new char[index];
int i = m, j = n;
while (i > 0 && j > 0) {
if (X.charAt(i-1) == Y.charAt(j-1)) {
lcs[--index] = X.charAt(i-1);
i--; j--;
} else if (L[i-1][j] > L[i][j-1])
i--;
else
j--;
}
return new String(lcs);
}
Console Output:
LCS Sequence: MJAU
Example 5: LCS for Multiple Sequences
Problem Statement:
Determine the LCS for three strings: "ABC", "AC", and "BC".
Solution Explanation:
The LCS for these sequences is "C". When dealing with more than two sequences, a multi-dimensional DP array is used.
int lcsMultiple(String X, String Y, String Z) {
int m = X.length(), n = Y.length(), o = Z.length();
int[][][] L = new int[m+1][n+1][o+1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= o; k++) {
if (i == 0 || j == 0 || k == 0)
L[i][j][k] = 0;
else if (X.charAt(i-1) == Y.charAt(j-1) && X.charAt(i-1) == Z.charAt(k-1))
L[i][j][k] = L[i-1][j-1][k-1] + 1;
else
L[i][j][k] = Math.max(Math.max(L[i-1][j][k], L[i][j-1][k]), L[i][j][k-1]);
}
}
}
return L[m][n][o];
}
Console Output:
Length of LCS: 1
