Longest Common Subsequence

1143. Longest Common Subsequence

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.

Analysis

​ It’s all about Selection or Ignore certain index of the sequence. Suppose we get the last letter in the sequence s and t, the letter are x and y. There are four cases

1. []

2. [x]

3. [y]

4. [x, y]

   So we can deduce the following function

1. dfs function

\[dfs(i,j) = \begin{cases} max(df(i-1, j), dfs(i, j-1), dfs(i-1, j-1)+1) & \text{s[i] = t[j]}\\ max(dfs(i-1, j), dfs(i, j-1), dfs(i-1, j-1)) & \text{s[i] != t[j]}\\ \end{cases}\] \[dfs(i,j) = max(dfs(i-1, j), dfs(i, j-1), dfs(i-1, j-1) + (s[i]=t[j]))\] \[dfs(i,j) = \begin{cases} dfs(i-1, j-1)+1 & \text{s[i] = t[j]}\\ max(dfs(i-1, j), dfs(i, j-1)) & \text{s[i] != t[j]}\\ \end{cases}\]

2. dp function

\[f(i,j) =  \begin{cases}     f[i-1][j-1]+1 & \text{s[i] = t[j]}\\     max(f[i-1][j], f[i][j-1) & \text{s[i] != t[j]}\\    \end{cases}\] \[f(i+1,j+1) =  \begin{cases}     f[i][j]+1 & \text{s[i+1] = t[j+1]}\\     max(f[i][j+1], f[i+1][j) & \text{s[i+1] != t[j+1]}\\    \end{cases}\]

Solutions

1. DFS way

class Solution:
    def longestCommonSubsequence(self, s: str, t: str) -> int:
        n = len(s)
        m = len(t)

        @cache
        def dfs(i, j):
            if i <0 or j < 0:
                return 0
            if s[i] == t[j]:
                return dfs(i-1,j-1) + 1
            else:
                return max(dfs(i-1, j), dfs(i, j-1))
        return dfs(n-1, m-1)

Input: abcde and ace

output:

3

Complexity

• Time complexity: ( O(nm) ), where ( n ) is the length of the input string. ( m ) is the length of the target strings.
• Space complexity: ( O(m) ), where ( m ) is the length of the target string.

2. DP two dim

class Solution:
    def longestCommonSubsequence(self, s: str, t: str) -> int:
        n = len(s)
        m = len(t)

        f = [[0] * (m+1) for _ in range(n+1)]

        for i, x in enumerate(s):
            for j, y in enumerate(t):
                f[i+1][j+1] = f[i][j] + 1 if x == y else max(f[i][j+1], f[i+1][j]) 
        return f[n][m]

Input: abcde and ace

output:

3

Complexity

• Time complexity: ( O(nm) ), where ( n ) is the length of the input string. ( m ) is the length of the target strings.
• Space complexity: ( O(m) ), where ( m ) is the length of the target string.

2. DP one dim

class Solution:
    def longestCommonSubsequence(self, s: str, t: str) -> int:
        n = len(s)
        m = len(t)

        f = [0] * (m+1)

        for i, x in enumerate(s):
            prev = f[0]
            for j, y in enumerate(t):
                temp = f[j+1]
                f[j+1] = prev + 1 if x == y else max(f[j+1], f[j])
                prev = temp
        
        return f[m]

Input: abcde and ace

output:

3

Complexity

• Time complexity: ( O(nm) ), where ( n ) is the length of the input string. ( m ) is the length of the target strings.
• Space complexity: ( O(m) ), where ( m ) is the length of the target string.