Longest Common Subsequence
In this page:
LCS Idea
The longest common subsequence of two strings is the longest sequence of characters that appears in both, in the same relative order, but not necessarily touching — ace is a subsequence of abcde even though the letters aren't adjacent.
Example: LCS Idea
#include <iostream>
using namespace std;
int main() {
string a = "abcde", b = "ace";
cout << "'" << b << "' is a subsequence of '" << a << "' (same order, not necessarily touching)";
return 0;
}public class Main {
public static void main(String[] args) {
String a = "abcde", b = "ace";
System.out.println("'" + b + "' is a subsequence of '" + a + "' (same order, not necessarily touching)");
}
}a, b = "abcde", "ace"
print(f"'{b}' is a subsequence of '{a}' (same order, not necessarily touching)")#include <stdio.h>
int main() {
char a[] = "abcde", b[] = "ace";
printf("'%s' is a subsequence of '%s' (same order, not necessarily touching)", b, a);
return 0;
}Login to try C/C++/Java code in the editor
DP State
dp[i][j] stores the LCS length using only the first i characters of the first string and the first j characters of the second, so filling this table prefix by prefix builds up to the answer for the full strings.
Example: DP State
#include <iostream>
using namespace std;
int main() {
int dp[6][4] = {0};
cout << "dp[i][j] = LCS length using first i chars of string1, first j chars of string2";
return 0;
}public class Main {
public static void main(String[] args) {
int[][] dp = new int[6][4];
System.out.println("dp[i][j] = LCS length using first i chars of string1, first j chars of string2");
}
}dp = [[0]*4 for _ in range(6)]
print("dp[i][j] = LCS length using first i chars of string1, first j chars of string2")#include <stdio.h>
int main() {
int dp[6][4] = {0};
printf("dp[i][j] = LCS length using first i chars of string1, first j chars of string2");
return 0;
}Login to try C/C++/Java code in the editor
Transition
If the current characters from both strings match, the LCS grows by one from the diagonal value (dp[i-1][j-1] + 1); if they don't match, the best you can do is the better of ignoring one character from either string (max of dp[i-1][j] and dp[i][j-1]).
Example: Transition
#include <iostream>
using namespace std;
int main() {
string a = "abcde", b = "ace";
int n = a.size(), m = b.size();
int dp[6][4] = {0};
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
dp[i][j] = a[i-1]==b[j-1] ? dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1]);
cout << "LCS length: " << dp[n][m];
return 0;
}public class Main {
public static void main(String[] args) {
String a = "abcde", b = "ace";
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++)
dp[i][j] = a.charAt(i-1)==b.charAt(j-1) ? dp[i-1][j-1]+1 : Math.max(dp[i-1][j], dp[i][j-1]);
System.out.println("LCS length: " + dp[n][m]);
}
}a, b = "abcde", "ace"
n, m = len(a), len(b)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
dp[i][j] = dp[i-1][j-1]+1 if a[i-1]==b[j-1] else max(dp[i-1][j], dp[i][j-1])
print("LCS length:", dp[n][m])#include <stdio.h>
#include <string.h>
int main() {
char a[] = "abcde", b[] = "ace";
int n = strlen(a), m = strlen(b);
int dp[6][4] = {0};
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (a[i-1]==b[j-1]) dp[i][j] = dp[i-1][j-1]+1;
else dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];
}
printf("LCS length: %d", dp[n][m]);
return 0;
}Login to try C/C++/Java code in the editor
Reconstruct LCS
Beyond just the length, tracing back through the filled table from the bottom-right corner — following diagonal moves on matches and the larger neighbor on mismatches — reconstructs the actual subsequence, not just its length.
Example: Reconstruct LCS
#include <iostream>
using namespace std;
int main() {
string a = "abcde", b = "ace";
int n = a.size(), m = b.size();
int dp[6][4] = {0};
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
dp[i][j] = a[i-1]==b[j-1] ? dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1]);
string result; int i = n, j = m;
while (i > 0 && j > 0) {
if (a[i-1] == b[j-1]) { result = a[i-1] + result; i--; j--; }
else if (dp[i-1][j] > dp[i][j-1]) i--;
else j--;
}
cout << "Reconstructed LCS: " << result;
return 0;
}public class Main {
public static void main(String[] args) {
String a = "abcde", b = "ace";
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++)
dp[i][j] = a.charAt(i-1)==b.charAt(j-1) ? dp[i-1][j-1]+1 : Math.max(dp[i-1][j], dp[i][j-1]);
StringBuilder result = new StringBuilder();
int i = n, j = m;
while (i > 0 && j > 0) {
if (a.charAt(i-1) == b.charAt(j-1)) { result.insert(0, a.charAt(i-1)); i--; j--; }
else if (dp[i-1][j] > dp[i][j-1]) i--;
else j--;
}
System.out.println("Reconstructed LCS: " + result);
}
}a, b = "abcde", "ace"
n, m = len(a), len(b)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
dp[i][j] = dp[i-1][j-1]+1 if a[i-1]==b[j-1] else max(dp[i-1][j], dp[i][j-1])
result = []
i, j = n, m
while i > 0 and j > 0:
if a[i-1] == b[j-1]:
result.append(a[i-1]); i -= 1; j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
print("Reconstructed LCS:", "".join(reversed(result)))#include <stdio.h>
#include <string.h>
int main() {
char a[] = "abcde", b[] = "ace", result[10];
int n = strlen(a), m = strlen(b), dp[6][4] = {0};
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (a[i-1]==b[j-1]) dp[i][j] = dp[i-1][j-1]+1;
else dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];
}
int i = n, j = m, k = 0;
while (i > 0 && j > 0) {
if (a[i-1] == b[j-1]) { result[k++] = a[i-1]; i--; j--; }
else if (dp[i-1][j] > dp[i][j-1]) i--;
else j--;
}
result[k] = '\0';
for (int x = 0; x < k/2; x++) { char t = result[x]; result[x] = result[k-1-x]; result[k-1-x] = t; }
printf("Reconstructed LCS: %s", result);
return 0;
}Login to try C/C++/Java code in the editor
Practice
LCS shows up directly in diff tools that highlight what changed between two versions of a file, and in DNA sequence comparison where researchers look for shared genetic patterns between two sequences.
Example: Practice
#include <iostream>
using namespace std;
int main() {
cout << "LCS powers diff tools (what changed between file versions) and DNA sequence comparison";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("LCS powers diff tools (what changed between file versions) and DNA sequence comparison");
}
}print("LCS powers diff tools (what changed between file versions) and DNA sequence comparison")#include <stdio.h>
int main() {
printf("LCS powers diff tools (what changed between file versions) and DNA sequence comparison");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 12 topics to unlock
0/12 topics done
Complete these topics first: