# 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()];

}