Longest Common Subsequence

Problem Statement

Given two strings text1 and text2, return the length of the longest common subsequence between the two strings if one exists, otherwise return 0.

A subsequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the relative order of the remaining characters.

  • For example, "cat" is a subsequence of "crabt".

A common subsequence of two strings is a subsequence that exists in both strings.

Example 1:

Input: text1 = "cat", text2 = "crabt"


Output: 3

Explanation: The longest common subsequence is “cat” which has a length of 3.

Example 2:

Input: text1 = "abcd", text2 = "abcd"


Output: 4

Example 3:

Input: text1 = "abcd", text2 = "efgh"


Output: 0

Constraints:

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

Aim for O(m*n) time and O(min(m, n)) space, where m and n are the lengths of the input strings.

Hint 1

Consider using dynamic programming.

Hint 2

Create a 2D array to store lengths of common subsequences of prefixes of the two strings.

Hint 3

The value at dp[i][j] represents the length of the longest common subsequence of text1[0...i-1] and text2[0...j-1].

Solution

Recursion

def longest_common_subsequence(text1: str, text2: str) -> int:
    def dfs(i, j):
        if i == len(text1) or j == len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1 + dfs(i + 1, j + 1)
        return max(dfs(i + 1, j), dfs(i, j + 1))


    return dfs(0, 0)

Time complexity: O(2 ^ {m + n}) Space complexity: O(m + n)

Where m is the length of the string text1 and n is the length of the string text2.