Problem Informations

• Problem Index: 1143
• Problem Link: Longest Common Subsequence
• Topics: String, Dynamic Programming

Problem Description

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

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.

• For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

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.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

• $1 \leq \text{text1.length}, \text{text2.length} \leq 1000$
• text1 and text2 consist of only lowercase English characters.

Intuition

The problem of finding the longest common subsequence (LCS) between two strings is a classical problem often solved using dynamic programming. The main idea is to break down the problem into smaller subproblems that can be solved recursively. My first thought was to leverage the properties of subsequences and utilize a 2D dynamic programming table to systematically evaluate possible subsequences and store intermediate results. This enables efficient computation by avoiding redundant evaluations.

Approach

The approach uses dynamic programming to find the length of the longest common subsequence between two strings, text1 and text2. The essence of this approach is to create a 2D array dp where dp[i][j] holds the length of the longest common subsequence of substrings text1[0...i-1] and text2[0...j-1].

1. Initialization: We initialize a 2D array dp of size (n+1) x (m+1), where n is the length of text1 and m is the length of text2. Each cell is initialized to zero. The extra row and column (beginning with index 0) allow us to handle the base cases effortlessly.

2. Iteration: We iterate through each character in text1 using an index i and each character in text2 using an index j. For every pair of characters (text1[i], text2[j]), we update the dp table based on the following cases:

   • If the characters text1[i] and text2[j] match, it means they can be part of a common subsequence. Hence, we can extend the previous common subsequence found by adding these characters. Therefore, dp[i+1][j+1] = dp[i][j] + 1.
   • If the characters do not match, the longest common subsequence up to this point could either exclude text1[i] or text2[j]. Therefore, we take the maximum value from considering either subproblem, dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]).

3. Result: After filling up the dp table, the desired length of the longest common subsequence will be found at dp[n][m].

This method runs in $O(n \times m)$ time complexity due to the double loop over the characters of both strings and uses $O(n \times m)$ space as well, due to the storage requirements of the dp table. Given the constraints, this is an efficient and feasible approach.

Code

C++

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        // Create a 2D DP array initialized to 0
        vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));

        // Iterate through each character of both strings
        for (int i = 0; i < text1.size(); i++) {
            for (int j = 0; j < text2.size(); j++) {
                // If characters match, increment the length of common subsequence
                if (text1[i] == text2[j]) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                } else {
                    // Otherwise, carry forward the maximum length found so far
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
                }
            }
        }

        // Return the length of the longest common subsequence
        return dp[text1.size()][text2.size()];
    }
};

Python

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # Create a 2D DP array initialized to 0
        dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]

        # Iterate through each character of both strings
        for i in range(len(text1)):
            for j in range(len(text2)):
                # If characters match, increment the length of common subsequence
                if text1[i] == text2[j]:
                    dp[i + 1][j + 1] = dp[i][j] + 1
                else:
                    # Otherwise, carry forward the maximum length found so far
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

        # Return the length of the longest common subsequence
        return dp[len(text1)][len(text2)]

Complexity

• Time complexity: The time complexity of the algorithm is $O(m \times n)$, where $m$ is the length of text1 and $n$ is the length of text2. This is because the algorithm uses a nested loop to iterate through each character in both strings, resulting in $m \times n$ iterations.

• Space complexity: The space complexity of the algorithm is $O(m \times n)$. The algorithm creates a 2D dynamic programming (DP) array dp of size $(m + 1) \times (n + 1)$ to store the lengths of the common subsequences at each point. Thus, the space required is proportional to the product of the lengths of the input strings.