We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Common Subsequence

Number: 1250

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Microsoft, DoorDash, Bloomberg, Meta, Oracle, Adobe, Yahoo, TikTok, Verily, Nutanix, Arista Networks, Citadel, Walmart Labs

Problem Description

Given two strings text1 and text2, determine the length of their longest common subsequence. A subsequence is derived from the original string by deleting some (or no) characters without changing the order of the remaining characters. If there is no common subsequence, return 0.

Key Insights

  • The problem is well-suited for a dynamic programming approach.
  • Use a 2D table where dp[i][j] stores the length of the longest common subsequence for text1[0...i-1] and text2[0...j-1].
  • If the characters match at the current position, extend the subsequence by 1 from dp[i-1][j-1]; otherwise, take the maximum from dp[i-1][j] or dp[i][j-1].
  • Filling the table in a bottom-up manner ensures that all subproblems are solved optimally.

Space and Time Complexity

Time Complexity: O(m * n), where m and n are the lengths of text1 and text2. Space Complexity: O(m * n) for maintaining the 2D DP table. Space can be optimized to O(min(m, n)) if needed.

Solution

This solution uses a dynamic programming approach with a 2D array (dp) to record the lengths of common subsequences at each substring pair. We initialize a table of dimensions (m+1) x (n+1) with zeros, where m and n are the lengths of text1 and text2. We iterate over both strings, comparing characters; if they match, we set dp[i][j] = dp[i-1][j-1] + 1, otherwise we choose the maximum from dp[i-1][j] and dp[i][j-1]. The final answer is found at dp[m][n].

Code Solutions

# Function to find the longest common subsequence length
def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    # Initialize a (m+1) x (n+1) DP table filled with zeros
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Build the DP table bottom-up
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            # If characters match, extend the subsequence length by 1
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                # Otherwise, choose the maximum from the left or top cell
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    return dp[m][n]

# Example usage
if __name__ == "__main__":
    text1 = "abcde"
    text2 = "ace"
    print(longestCommonSubsequence(text1, text2))  # Output: 3
← Back to All Questions