115. Distinct Subsequences

Problem¶

Count how many ways t can be formed by deleting characters from s without changing the order of the remaining characters. Different choices of source indices count separately.

s = "rabbbit", t = "rabbit"
Choose 2 of the 3 consecutive b's in s.
Output: 3

Key trick¶

Use dynamic programming where dp[j] counts ways to form t[:j] from the processed part of s; update j backward so each source character is used at most once.

Trap¶

Updating dp from left to right reuses the current source character multiple times. Also, when characters match, add both possibilities: skip the source character or use it.

Why is it interesting?¶

It compresses a natural two-dimensional prefix DP into one dimension by choosing the update order carefully.

Python solution¶

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        if len(t) > len(s):
            return 0

        # dp[j] is the number of ways to form t[:j] from the source
        # characters processed so far.
        dp = [0] * (len(t) + 1)
        dp[0] = 1  # The empty target is formed by choosing nothing.

        for ch in s:
            # Iterate backward so dp[j - 1] still excludes ch.
            for j in range(len(t), 0, -1):
                if ch == t[j - 1]:
                    dp[j] += dp[j - 1]

        return dp[-1]

Time complexity: \(O(|s||t|)\).

Space complexity: \(O(|t|)\).

Comment on my solution¶

Your two-dimensional DP definition is correct:

\[ dp[i][j] = \text{ways to form } t[:j] \text{ from } s[:i]. \]

The recurrence is:

\[ dp[i][j] = \begin{cases} dp[i-1][j] + dp[i-1][j-1], & s[i-1] = t[j-1] \\ dp[i-1][j], & s[i-1] \ne t[j-1]. \end{cases} \]

Your missing insight is that a matching character creates two choices: skip it or use it. There is no need to reverse the problem or fill columns first; a row-by-row DP works directly and can be compressed to one array by updating backward. The submitted method is incomplete, so it cannot yet be tested.

# Ideas:
# - DFS backtracking is exponential so don't work with size input
# - 2D DP on prefixes

# - dp[i][j] number of subsequences of s[:i] that matches t[:j]
# - answer is: dp[-1][-1]
# - transition:
#   - if we take s[i - 1] it will be at the end of the every sequences
#     and so must be equal to t[j - 1]
#   - if s[i - 1] != t[j - 1]
#     - s[i - 1] can't end a previous sub sequence matching t[:j - 1]
#       - so we must take dp[i - 1][j]
#                       r
#                     r a
#                   r a b
#                 r a b b
#               r a b b i
#          "" r a b b i t
#       ""          |
#       r           |
#      ra           |
#     rab           |
#    rabb   --------1 0
#   rabbb
#  rabbbi
# rabbbit
#
# - With this order it seems we have to loop over string t first
#   - meaning we fill the column first
#   - maybe we could just swap row and columns too
# - I don't think I'm looking at the problem the correct way
# - maybe we can reverse the problem
#  - and count the combination of removal in string s

class Solution:
    def numDistinct(self, s: str, t: str) -> int:

You are missing the DP base cases, and your loops incorrectly process index 0.

dp[i][0] = 1: the empty target can always be formed by selecting nothing.
dp[0][j] = 0 for j > 0: a non-empty target cannot be formed from an empty source.
The recurrence must start at i = 1 and j = 1.
In Python, s[i - 1] when i == 0 means s[-1], so your code silently uses the last character and the last DP row instead of going out of bounds.

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # There is exactly one way to form an empty target:
        # choose no characters from the source.
        for i in range(m + 1):
            dp[i][0] = 1

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                # Always allowed: skip s[i - 1].
                dp[i][j] = dp[i - 1][j]

                if s[i - 1] == t[j - 1]:
                    # Also allowed: use s[i - 1] to match t[j - 1].
                    dp[i][j] += dp[i - 1][j - 1]

        return dp[m][n]

The recurrence is:

\[ dp[i][j] = dp[i-1][j] + \begin{cases} dp[i-1][j-1], & s[i-1] = t[j-1] \\ 0, & s[i-1] \ne t[j-1] \end{cases} \]

Here, dp[i - 1][j] skips the current source character, while dp[i - 1][j - 1] uses it.

Time complexity: \(O(mn)\).

Space complexity: \(O(mn)\).

# Implemented after reading AI comments on my Ideas
#
# Wrong Answer: 15/66 testcases passed
# "rabbbit", "rabbit"
# Output: 0
# Expected: 3
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            for j in range(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[-1][-1]