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

Distinct Subsequences

Difficulty: Hard

Problem Description

Given two strings s and t, return the number of distinct subsequences of s which equals t.

Key Insights

  • A subsequence can be derived from another string by deleting some characters without changing the order of the remaining characters.
  • We can use dynamic programming to count the number of distinct subsequences.
  • A 2D table can be used where dp[i][j] represents the number of distinct subsequences of s[0...i] that equals t[0...j].

Space and Time Complexity

Time Complexity: O(m * n), where m is the length of string s and n is the length of string t.
Space Complexity: O(m * n), due to the 2D DP table used for storing results.

Solution

We will utilize a dynamic programming approach with a 2D table to keep track of the number of ways to form string t from string s. The table will have dimensions (m+1) x (n+1), where m is the length of s and n is the length of t. The base case will be initialized such that dp[0][0] = 1, indicating that there is one way to form an empty string from an empty string. We will iterate through the characters of both strings, updating our table based on whether characters match or not.

Code Solutions

def numDistinct(s: str, t: str) -> int:
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for j in range(n + 1):
        dp[0][j] = 0 if j > 0 else 1  # Only one way to form an empty t
    
    for i in range(1, m + 1):
        dp[i][0] = 1  # One way to form an empty t from any s
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j]
    
    return dp[m][n]
← Back to All Questions