Leetcode 1143: Longest Common Subsequence

Input: You are given two strings text1 and text2. The characters in each string are lowercase English letters.

Example: Input: text1 = 'apple', text2 = 'applause'

Constraints:

• 1 <= text1.length, text2.length <= 1000

• text1 and text2 consist of only lowercase English characters.

Output: Return the length of the longest common subsequence between text1 and text2.

Example: Output: 5

Constraints:

• The output will be a single integer representing the length of the longest common subsequence.

Goal: Find the length of the longest common subsequence by comparing characters of both strings and using dynamic programming to store the results of overlapping subproblems.

Steps:

• 1. Create a 2D DP table to store the lengths of longest common subsequences for different substrings.

• 2. Iterate through both strings. If characters match, add 1 to the value of the previous common subsequence.

• 3. If characters do not match, take the maximum length from either of the previous two subsequences.

• 4. The final value in the DP table will be the length of the longest common subsequence.

Goal: The problem must be solved efficiently with respect to both time and space complexity.

Steps:

• 1 <= text1.length, text2.length <= 1000

• 1 <= text2.length <= 1000

Assumptions:

• Both text1 and text2 will consist only of lowercase English characters.

• The length of both text1 and text2 will be between 1 and 1000.

• Input: Input: text1 = 'apple', text2 = 'applause'

• Explanation: In this example, the longest common subsequence between 'apple' and 'applause' is 'apple', which has a length of 5.

• Input: Input: text1 = 'happy', text2 = 'sad'

• Explanation: In this example, the longest common subsequence between 'happy' and 'sad' is 'a', which has a length of 1.

• Input: Input: text1 = 'cat', text2 = 'dog'

• Explanation: In this example, there is no common subsequence between 'cat' and 'dog', so the result is 0.

Approach: The problem can be solved using dynamic programming to calculate the longest common subsequence by comparing characters and storing results for overlapping subproblems.

Observations:

• The problem can be efficiently solved using dynamic programming with a 2D table.

• The key observation is that we need to store intermediate results to avoid redundant calculations, which makes dynamic programming a good choice.

Steps:

• 1. Initialize a 2D DP table with dimensions (text1.length + 1) x (text2.length + 1).

• 2. Loop through both strings. If characters match, increment the previous common subsequence length by 1. Otherwise, take the maximum length from either the top or left cell in the DP table.

• 3. Return the value in the bottom-right corner of the table, which contains the length of the longest common subsequence.

Empty Inputs:

• The case where one of the strings is empty should be handled by returning 0.

Large Inputs:

• The algorithm must be optimized to handle large inputs efficiently (up to 1000 characters).

Special Values:

• The case where both strings are the same should return the length of the string.

Constraints:

• Ensure that the DP table is initialized correctly and that the algorithm runs within the problem's constraints.

int longestCommonSubsequence(string t1, string t2) {
    int n1 = t1.size(), n2 = t2.size();
    vector<vector<int>> dp(n1 +1, vector<int>(n2+1, 0));
    for(int i = 0; i < n1; i++)
        for(int j = 0; j < n2; j++)
            if(t1[i] == t2[j])
                dp[i+1][j+1] = dp[i][j] +1;
    else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
    
    return dp[n1][n2];
}

1 : Function Definition

int longestCommonSubsequence(string t1, string t2) {

This defines the function `longestCommonSubsequence`, which takes two input strings `t1` and `t2` and returns the length of their longest common subsequence.

2 : Variable Declaration

    int n1 = t1.size(), n2 = t2.size();

This declares two integer variables `n1` and `n2`, which store the lengths of the input strings `t1` and `t2` respectively.

3 : Matrix Initialization

    vector<vector<int>> dp(n1 +1, vector<int>(n2+1, 0));

This initializes a 2D vector `dp` of size `(n1+1) x (n2+1)`, where each element is initialized to 0. This matrix will be used to store the length of the longest common subsequence for substrings of `t1` and `t2`.

4 : Loop Initialization

    for(int i = 0; i < n1; i++)

This begins a loop that iterates over each character of the first string `t1`.

5 : Inner Loop

        for(int j = 0; j < n2; j++)

This begins an inner loop that iterates over each character of the second string `t2`.

6 : Condition Check

            if(t1[i] == t2[j])

This checks if the characters `t1[i]` and `t2[j]` are equal.

7 : Dynamic Programming Update

                dp[i+1][j+1] = dp[i][j] +1;

If the characters are equal, this updates the value of `dp[i+1][j+1]` to `dp[i][j] + 1`, meaning that the LCS length for this pair of substrings is extended by 1.

8 : Else Condition

    else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);

If the characters are not equal, this sets `dp[i+1][j+1]` to the maximum of `dp[i][j+1]` and `dp[i+1][j]`, representing the longest subsequence found by excluding either the current character of `t1` or `t2`.

9 : Return Statement

    return dp[n1][n2];

This returns the value stored in `dp[n1][n2]`, which holds the length of the longest common subsequence of the entire strings `t1` and `t2`.

Best Case: O(n * m)

Average Case: O(n * m)

Worst Case: O(n * m)

Description: The time complexity is O(n * m) where n is the length of text1 and m is the length of text2.

Best Case: O(n * m)

Worst Case: O(n * m)

Description: The space complexity is O(n * m) due to the DP table storing intermediate results for all substrings.

Leetcode 1143: Longest Common Subsequence

Explore →