1143.Longest_Common_Subsequence(Medium).md

1143. Longest Common Subsequence (Medium)

Date and Time: Aug 25, 2024, 0:11 (EST)

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

Question:

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 <= text1.length, text2.length <= 1000

• text1 and text2 consist of only lowercase English characters.

Walk-through:

First Approach:

1. Build a dp table (len(text1) + 1) * (len(text2) + 1) with value 0. And we store each dp[r][c] to be the current longest common subsequence length.

2. If text1[r-1] == text2[c-1] that means we have a same character, and we should update dp[r][c] = dp[r-1][c-1] + 1, which is the previous LCS length we know, plus this current match.

3. If they don't match, we should update dp[r][c] = max(dp[r-1][c], dp[r][c-1]).

4. Finally, return the last grid of dp.

Note that we compare two texts by text1[r-1] and text2[c-1] instead of text1[r] and text2[c], because we have an extra 0 in front of each column and each row for the base case.

Example 1:
            a c e
          0 0 0 0
        a 0 1 1 1
        b 0 1 1 1
        c 0 1 2 2
        d 0 1 2 2
        e 0 1 2 3

Example 2:
            a b c
          0 0 0 0
        a 0 1 1 1
        b 0 1 2 2
        c 0 1 2 3

Similar Approach: We can also start filling the dp backward from bottom up, right to left.

Optimized Approach: The optimized solution we just use an 1 x n array as dp instead of having a 2d dp. Which saves the previous row's value. Each time in the loop of c, we use tmp to store the current value of dp[c], because we are going to overwrite it later with either they have a match or not.

If they are matched, we udpate dp[c] = 1 + prev, because prev is [r-1][c-1]. If they are not matched, we upate dp[c] = max(dp[c], dp[c-1]), we are finding the max([r-1][c], [r][c-1]).

After updating dp[c], we can update prev = tmp, which has the same effect as dp[r-1][c-1], the value of previous column.

Python Solution:

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # Q: Return the longest common subsequence
        # S: dp[i][j] is the longest common subsequence
        # If text1[i] == text2[j]: dp[i][j] = dp[i-1][j-1] + 1
        # Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        # TC: O(n*m), n=len(text1), m=len(text2), SC: O(n*m)

        #     a b c
        #   0 0 0 0
        # a 0 1 1 1
        # b 0 1 2 2
        # c 0 1 2 3

        dp = [[0] * (len(text2)+1) for _ in range(len(text1)+1)]
        for i in range(len(text1)):
            for j in range(len(text2)):
                if text1[i] == text2[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[-1][-1]

Time Complexity: $O(m * n)$, m is length of text1, n is length of text2.
Space Complexity: $O(m * n)$

Python DP Optimized Solution:

Note that we now don't need to loop over an extra row in the beginning, so just range(len(text1)).

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        prev = [0] * (len(text2)+1)
        for r in range(len(text1)):
            dp = [0] * (len(text2)+1)
            for c in range(1, len(text2)+1):
                if text1[r] == text2[c-1]:
                    dp[c] = prev[c-1] + 1
                else:
                    dp[c] = max(prev[c], dp[c-1])
            prev = dp
        return prev[-1]

Time Complexity: $O(m * n)$, m is length of text1, n is length of text2.
Space Complexity: $O(n)$, now we are only storing the length of text2.

Python Optimized with 1 Variable:

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [0] * (len(text2) + 1)    # For previous row
        for r in range(1, len(text1)+1):
            prev = 0    # Default val for each row's prev
            for c in range(1, len(text2)+1):
                tmp = dp[c]    # [r-1][c]
                if text1[r-1] == text2[c-1]:
                    dp[c] = 1 + prev
                else:
                    dp[c] = max(dp[c], dp[c-1])
                prev = tmp    # [r-1][c-1]
        return dp[-1]

Time Complexity: $O(m * n)$
Space Complexity: $O(n)$