Longest Common Subsequence

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.

The longest common subsequence is "cat" which has a length of 3.

Approach

Use a 2D DP table where dp[i][j] is the LCS length for prefixes text1[:i] and text2[:j]. If the characters match, take dp[i-1][j-1] + 1; otherwise take the max of left and top.

Why It Works

The LCS either uses the last characters (when they match) or excludes one of them. This recurrence explores both cases and builds up optimal lengths for all prefix pairs, ensuring dp[m][n] is the correct LCS length.

Complexity

• Time: O(m * n)
• Space: O(m * n)

Reference Implementation (Python)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        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])
        return dp[m][n]