Leetcode: Longest Common Subsequence

This is asked at Amazon, Microsoft, Google, Facebook, TikTok, and Uber, to name a few and is as follows: 

Given 2 strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0. 

A subsequence is a string is a new string generated from the original string with some characters deleted without changing the relative order. A common subsequence of 2 strings is a subsequence that is common to both strings. 

Example 1:

Input: text1: "abcde", text2 = "ace"

Output: 3

Explanation: Longest common Subsequence is "ace" where the length will equate to 3.

Example 2: 

Input: text1: "abc", text2 = "def"

Explanation: There is no common subsequence; so, the result is 0.

 

Git needs to use this algorithm when merging branches and things are also used in bioinformatics to measure the similarity between genetic codes.

A common subsequence is a sequence of letters that appears in both strings. Notice that the lines do not cross over in this example. 

So we should do DP[i][j] represents the longest common subsequence from text 0...i and text2 0 ... j.  

DP[i][j] = DP[i - 1][j - 1] + 1 if text1[i] == text2[j]. Else we just take the maximum of DP[i - 1][j] and DP[i][j - 1].

We want to perform dynamic programming with space optimization. Let's first look into the dynamic programming approach, without space optimization. We implement the dynamic programming, as follows: 

class Solution {

    public int longestCommonSubsequence(String text1, String text2) {

        int[][] dpGrid = new int[text1.length + 1][text2.length + 1];

        //iterate backwards from the furthest index

        for(int col = text2.length() - 1; col >= 0; col--) {

            for(int row = text1.length() - 1; row >= 0; row--) {

                //increment by 1 as we found the subsequence

                if (text1.charAt(row) == text2.charAt(col)) {

                    dpGrid[row][col] = 1 + dpGrid[row + 1][col + 1];

                } else {

                    //else return to the maximum of what was known in the past. 

                    dpGrid[row][col] = Math.max(dpGrid[row + 1][col], dpGrid[row][col + 1]);

                }

            }

        }

        return dpGrid[0][0];     

    }

}