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

Distinct Subsequences

Number: 115

Difficulty: Hard

Paid? No

Companies: Salesforce, Amazon, Microsoft, Google, Oracle, Trilogy, Apple, Bloomberg, TikTok

Problem Description

Given two strings s and t, return the number of distinct subsequences of s that equal t. 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.

Key Insights

  • Use dynamic programming to build the solution by comparing characters of s and t.
  • Define a 2D dp table where dp[i][j] represents the number of ways to form the first j characters of t using the first i characters of s.
  • The recurrence relation:
    • If s[i-1] equals t[j-1], then include both the cases of matching this character as well as skipping it: dp[i][j] = dp[i-1][j-1] + dp[i-1][j].
    • If they do not match, then simply skip the current character of s: dp[i][j] = dp[i-1][j].
  • Initialize dp[i][0] = 1 for all i since an empty t can always be formed.
  • The final answer is dp[s.length][t.length].

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of s and m is the length of t. Space Complexity: O(n * m), which can be optimized to O(m) with careful row reuse.

Solution

We use a dynamic programming approach with a 2D table. The table has dimensions (len(s) + 1) x (len(t) + 1). Each cell dp[i][j] stores the number of distinct subsequences from the first i characters of s that match the first j characters of t.

Steps:

  1. Initialize dp[i][0] = 1 for every i, because an empty t is a subsequence of any prefix of s.
  2. Iterate over each character of s (outer loop) and for each, iterate over t (inner loop).
  3. For every character in s, if it equals the current character in t, update dp[i][j] as the sum of the ways by using or skipping this character. Otherwise, carry over the previous count.
  4. Return dp[len(s)][len(t)] as the result.

Code Solutions

# Python solution for Distinct Subsequences
def numDistinct(s: str, t: str) -> int:
    # Get lengths of the strings s and t
    m, n = len(s), len(t)
    # Initialize a dp table with (m+1) rows and (n+1) columns filled with 0
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Base case: An empty string t (j = 0) is a subsequence of any prefix of s, so set dp[i][0] = 1
    for i in range(m + 1):
        dp[i][0] = 1

    # Fill the dp table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            # If the current characters match, add the count of sequences by either using or skipping s[i-1]
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
            else:
                # If they do not match, skip s[i-1]
                dp[i][j] = dp[i - 1][j]
    # The answer is the way to form all of t from all of s
    return dp[m][n]

# Example usage:
print(numDistinct("rabbbit", "rabbit"))  # Output: 3
← Back to All Questions