Longest Common Subsequence

As a senior engineer interested in practice data structures and algorithms, you may encounter a popular problem known as the Longest Common Subsequence (LCS) problem.

The LCS problem involves finding the length of the longest common subsequence between given strings str1 and str2.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements from the original sequence, without changing the order of the remaining elements.

For example, given the strings str1 = "AGGTAB" and str2 = "GXTXAYB", the longest common subsequence is GTAB, so the length of the LCS is 4.

To solve the LCS problem, we can use dynamic programming. We can define a 2D array dp of size (m + 1) x (n + 1), where m and n are the lengths of str1 and str2 respectively.

We can then use recursive function longestCommonSubsequence to calculate the length of the LCS as follows:

1// replace with your Java logic here
2String str1 = "AGGTAB";
3String str2 = "GXTXAYB";
4int m = str1.length();
5int n = str2.length();
6int[][] dp = new int[m + 1][n + 1];
7int len = longestCommonSubsequence(str1, str2, m, n, dp);
8System.out.println("The length of the longest common subsequence is: " + len);

The longestCommonSubsequence function takes the two strings str1 and str2, along with their lengths m and n respectively, and the 2D array dp as parameters. It uses memoization to avoid redundant calculations of the LCS length.

In the longestCommonSubsequence function, we check the base cases where m or n is 0, which means one of the strings is empty. In this case, the length of the LCS is 0.

If the LCS length for the current characters str1[m - 1] and str2[n - 1] has already been calculated and stored in dp[m][n], we return that value.

Otherwise, we compare the last characters str1[m - 1] and str2[n - 1]. If they are the same, we increment the LCS length by 1 and recursively call longestCommonSubsequence for the remaining characters m - 1 and n - 1.

If the last characters are different, we take the maximum of the LCS lengths obtained by removing the last character of str1 (keeping str2 intact) and removing the last character of str2 (keeping str1 intact).

Finally, we store the calculated LCS length in dp[m][n] and return that value.

By using dynamic programming and memoization, we can efficiently solve the longest common subsequence problem. The time complexity of the dynamic programming solution is O(mn), where m and n are the lengths of str1 and str2 respectively.

xxxxxxxxxx

}

class Main {

  public static void main(String[] args) {

    // replace with your Java logic here

    String str1 = "AGGTAB";

    String str2 = "GXTXAYB";

    int m = str1.length();

    int n = str2.length();

    int[][] dp = new int[m + 1][n + 1];

    int len = longestCommonSubsequence(str1, str2, m, n, dp);

    System.out.println("The length of the longest common subsequence is: " + len);

  }

​

  private static int longestCommonSubsequence(String str1, String str2, int m, int n, int[][] dp) {

    if (m == 0 || n == 0) {

      return 0;

    }

​

    if (dp[m][n] != 0) {

      return dp[m][n];

    }

​

    if (str1.charAt(m - 1) == str2.charAt(n - 1)) {

      dp[m][n] = 1 + longestCommonSubsequence(str1, str2, m - 1, n - 1, dp);

    } else {

      dp[m][n] = Math.max(longestCommonSubsequence(str1, str2, m - 1, n, dp),

          longestCommonSubsequence(str1, str2, m, n - 1, dp));

    }

​

    return dp[m][n];