Longest Common Subsequence medium

Problem Statement

Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, "ace" is a subsequence of "abcde"). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Example 1:

Input: text1 = "abcde", text2 = "ace" Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc" Output: 3 Explanation: The longest common subsequence is "abc" and its length is 3.

Steps:

1. Dynamic Programming Approach: We'll use a 2D array dp where dp[i][j] represents the length of the longest common subsequence of text1[0...i-1] and text2[0...j-1].

2. Base Cases:

   • dp[0][j] = 0 for all j (empty text1)
   • dp[i][0] = 0 for all i (empty text2)

3. Recursive Relation:

   • If text1[i-1] == text2[j-1], it means we found a common character. We can extend the LCS by 1: dp[i][j] = dp[i-1][j-1] + 1.
   • If text1[i-1] != text2[j-1], we need to consider two possibilities: either the last character of text1 is not part of the LCS, or the last character of text2 is not part of the LCS. We take the maximum of these two possibilities: dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]).

4. Iteration: We iterate through the dp array, filling it according to the recursive relation.

5. Result: The final answer is dp[text1.length()][text2.length()].

Explanation:

The dynamic programming approach efficiently avoids redundant calculations by storing the results of subproblems. The recursive relation ensures that we explore all possible common subsequences and choose the longest one. The 2D array dp acts as a memoization table, speeding up the process significantly.

Code:

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();

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

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[m][n];
    }
}

Complexity:

• Time Complexity: O(m*n), where 'm' and 'n' are the lengths of the input strings. This is because we iterate through the entire dp array.
• Space Complexity: O(m*n), the space used by the dp array. We could optimize this to O(min(m,n)) using space optimization techniques (only storing the previous row of the dp array).