1143. Longest Common Subsequence

[goungoun]

Intuition

A common subsequence of two strings is a subsequence that is common to both strings. The longest common subsequence might need max function. No transposition, only delete operation can be performed in any places to extract the common sequence.

Assumption

By its nature of delete operation:

• Cannot be consecutive after deletion
• No change relative order

Constraints:

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English characters.

Approach

Bottom up DP.

Steps:

• Make a table using Text1 as a row, Text2 as a column
• The first row is without any char from Text 1. Fill it all zero.
• The first col is without any char from Text 2. Fill it all zero.
• Increase the row index and col index, compare a single char from Text1 and Text2 in each index
• If chars are the same, increase one from the diagonal position. Why diagonal? Because +1 without the same character from the each text. e.g, LCS('ABC', 'AC') = LCS('AB', 'A') + 1
• If different, get the previous max subsequence.

Solution

It requires maximum (1000 + 1) x (1000 +1) dp table.

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if not text1 or not text2:
            return 0

        l1 = len(text1)+1 if text1 else 0
        l2 = len(text2)+1 if text2 else 0 
        
        # longest[r][c] : the length of LCS of the sequences text1[:r] and text2[:c]
        longest = [[0]*l2 for _ in range(l1)]

        for r in range(1, l1):
            for c in range(1, l2):
                if text1[r-1] == text2[c-1]:
                    longest[r][c] = 1 + longest[r-1][c-1]
                else:
                    longest[r][c] = max(
                        longest[r-1][c], 
                        longest[r][c-1]
                        )

        return longest[-1][-1]

Performance

Replace the matrix longest to two array lists, curr and prv

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if not text1 or not text2:
            return 0

        l1 = len(text1)+1 if text1 else 0
        l2 = len(text2)+1 if text2 else 0 
        
        curr = [0]*l2
        prv = [0]*l2

        for r in range(1, l1):
            for c in range(1, l2):
                if text1[r-1] == text2[c-1]:
                    curr[c] = 1 + prv[c-1]
                else:
                    curr[c] = max(
                        prv[c],
                        curr[c-1]
                        )
            prv = curr.copy()

        return prv[-1]

Issue

prv = curr resulted wrong result.

Test Case:
text1 = "abcba"
text2 ="abcbcba"
Output - 6
Expected - 5

prv = curr.copy() resolved the issue.

Complexity

Full Tabular:

• Time complexity: O(mn) beats 79.45%
• Space complexity: O(mn) beats 52.78%

Optimized:

• Time complexity: O(mn), beats 93.88 %
• Space complexity: O(n), beats 91.28 %

Conclusion

Improved on the time and space use
Fixed bug memory reference

https://github.com/goungoun/leetcode/blob/main/DynamicProgramming/longest_common_subsequence.py