Edit distance variant — Longest common subsequence

The longest common subsequence is a very popular DP problem whereby we try to figure out the longest common subsequence between two strings

For example : “democrat”, “republican”

The longest common subsequence between the above two strings is “eca”

To figure out the length of LCS, we can build a recurrence relation as mentioned below:

String A = (0,….i,…)

String B = (0,….,j,…)

dp[i][j] = 1 + dp[i-1][j-1] , if A[i] == B[j]

dp[i][j] = Maximum(dp[i-1][j], dp[i][j-1]), if A[i] != B[j]

Sample implementation for leetcode :

public int longestCommonSubsequence(String text1, String text2) {
int[][] dp = new int[text1.length() + 1][text2.length() + 1];
for (int i = 1; i <= text1.length(); i++) {
for (int j = 1; j <= text2.length(); j++) {
char chI = text1.charAt(i - 1);
char chJ = text2.charAt(j - 1);
if(chI == chJ) {
dp[i][j] = dp[i-1][j-1] + 1;
}
if(dp[i-1][j] > dp[i][j])
dp[i][j] = dp[i-1][j];
if(dp[i][j-1] > dp[i][j])
dp[i][j] = dp[i][j-1];
}
}
return dp[text1.length()][text2.length()];
}

More from Sweta Barman

I’m a software engineer with a strong interest in algorithms. I love solving puzzles and love the aha moment of arriving at a solution after hours of struggle.