1143. Longest Common Subsequence

MediumLeetCode

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.

How to solve the problem

• Recursion with Memoization

# Approach 1: Recursion with Memoization
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n = len(text1)
        m = len(text2)

        @cache
        def dfs(i, j):
            # Base case: empty string, LCS is 0.
            if i < 0 or j < 0:
                return 0
            # If characters match, include them in LCS.
            if text1[i] == text2[j]:
                return dfs(i - 1, j - 1) + 1
            # If characters don't match, take max of excluding one char.
            return max(dfs(i - 1, j), dfs(i, j - 1))

        # Start from the end of both strings.
        return dfs(n - 1, m - 1)

• Optimized Dynamic Programming

# Approach 2: Optimized Dynamic Programming
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # DP array: f[j] stores LCS length for text1 (current char) and text2[:j].
        f = [0] * (len(text2) + 1)
        # Iterate through each char 'x' in text1.
        for x in text1:
            # 'pre' holds f[j] from previous iteration (row).
            pre = 0
            # Iterate through each char 'y' in text2.
            for j, y in enumerate(text2):
                # Save f[j+1] before update (for next 'pre').
                tmp = f[j + 1]
                # DP transition: if chars match, add 1 to diagonal (pre);
                # else, take max of skipping x (f[j+1]) or skipping y (f[j]).
                f[j + 1] = pre + 1 if x == y else max(f[j + 1], f[j])
                # Update 'pre' for next iteration.
                pre = tmp
        # f[-1] contains the final LCS length.
        return f[-1]

Complexity

• Approach 1 (Recursion with Memoization): Time complexity: O(n * m), Space complexity: O(n * m)
• Approach 2 (Optimized DP): Time complexity: O(n * m), Space complexity: O(m)