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