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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Common Subsequence

Difficulty: Medium

Problem Description

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 deleted without changing the relative order of the remaining characters.

Key Insights

  • A common subsequence is a sequence that appears in both strings in the same order.
  • The problem can be solved using dynamic programming to build a 2D table that tracks the lengths of common subsequences.
  • The solution involves comparing characters of both strings and updating the table based on matches or mismatches.

Space and Time Complexity

Time Complexity: O(m * n), where m and n are the lengths of text1 and text2, respectively.
Space Complexity: O(m * n) for the DP table.

Solution

To solve the problem, we can use a dynamic programming approach. We create a 2D array (table) where dp[i][j] represents the length of the longest common subsequence of the first i characters of text1 and the first j characters of text2.

  1. Initialize a table with dimensions (m+1) x (n+1) filled with zeros, where m and n are the lengths of text1 and text2.
  2. Iterate through each character of both strings.
  3. If the characters match, update the table at dp[i][j] to be 1 + dp[i-1][j-1].
  4. If the characters do not match, update the table at dp[i][j] to be the maximum of dp[i-1][j] and dp[i][j-1].
  5. The value in the bottom-right cell of the table (dp[m][n]) will give the length of the longest common subsequence.

Code Solutions

def longestCommonSubsequence(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] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    return dp[m][n]
← Back to All Questions