1143. Longest Common Subsequence

https://leetcode.com/problems/longest-common-subsequence/description/

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For example, “ace” is a subsequence of “abcde”.

To solve this problem, we can use dynamic programming. We can create a 2D array dp of size (m+1) x (n+1), where m and n are the lengths of text1 and text2, respectively. The value dp[i][j] represents the length of the longest common subsequence of text1[:i] and text2[:j].

We can fill up the dp array as follows:

• If either text1 or text2 is empty, then the longest common subsequence is 0.
• If the last characters of text1 and text2 match (i.e., text1[i-1] == text2[j-1]), then the longest common subsequence is 1 plus the length of the longest common subsequence of text1[:i-1] and text2[:j-1].
• Otherwise, we can either exclude the last character of text1 and find the longest common subsequence of text1[:i-1] and text2[:j], or exclude the last character of text2 and find the longest common subsequence of text1[:i] and text2[:j-1]. We take the maximum of these two values.

Finally, the length of the longest common subsequence of text1 and text2 is given by dp[m][n].

Here’s the Python code implementing this approach:

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n+1) for _ in range(m+1)]
        
        for i in range(1, m+1):
            for j in range(1, n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        
        return dp[m][n]

Time Complexity

O(m*n), where m and n are the lengths of text1 and text2, respectively. We need to fill up the dp array of size (m+1) x (n+1).

Space Complexity

O(m*n), we need to store the dp array.