Longest Common Subsequence [LC#1143]

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.

Dynamic programming approach

• dp[i][j] contains length of longest subsequence by using first i-1 characters of first string and j-1 characters of second string.
• dp[i][0] = 0 and dp[0][j] = 0
• $T(n) = O(mn)$; $S(n) = O(mn)$

    def longest_common_subsequence(text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)
          
        # Create a 2D array to store lengths of longest common subsequence.
        dp = [[0] * (n + 1) for _ in range(m + 1)]
          
        # Build the dp array
        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])
          
        # The length of the longest common subsequence is in dp[m][n]
        return dp[m][n]
  

Dynamic programming approach with space optimisation

• $T(n) = O(mn)$ ; $S(n) = O(\min\{m,n\})$

    def longest_common_subsequence(text1: str, text2: str) -> int:
        if len(text2) > len(text1):
            return longest_common_subsequence(text2, text1)
  
        m = len(text1)
        n = len(text2)
  
        prev = [0] * (n + 1)
        curr = [0] * (n + 1)
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    curr[j] = prev[j - 1] + 1
                else:
                    curr[j] = max(curr[j - 1], prev[j])
            prev, curr = curr, prev
        return prev[n]