Distinct Subsequences (LeetCode 115)

The problem

Given strings s and t, return the number of distinct ways to pick characters of s (keeping their order) that spell exactly t. Two ways are different if they use a different set of positions in s.

Input:  s = "rabbbit", t = "rabbit"
Output: 3

s has three bs and t needs two, so you can drop any one of the three: 3 ways.

How to think about it

Start with brute force. Try every subsequence of s with length len(t) and count the ones equal to t. That is up to C(m, n) subsequences, exponential in general.

The key insight: each character of s is either used or not. Let dp[i][j] be the number of ways to form t[:j] from s[:i]. The character s[i-1] can always be skipped, giving dp[i-1][j] ways. If it matches t[j-1], it can also be used as the last character, giving dp[i-1][j-1] more. So dp[i][j] = dp[i-1][j] + (dp[i-1][j-1] if s[i-1] == t[j-1]). The base case is dp[i][0] = 1: there’s exactly one way to form the empty string.

Compress to one row, but run j backwards. Row i only reads row i-1, so keep one array. The “skip” case is free: dp[j] already holds the old value. For the “use” case you need the old dp[j-1]. Going right to left, dp[j-1] hasn’t been updated yet in this pass, so it still holds the previous row’s value. Going left to right would let one character of s be used twice.

Which pattern is this? 2-D DP over two sequences, counting. The tell is “how many ways does one string occur inside another as a subsequence”.

Approach

1. Make dp of length len(t) + 1 with dp[0] = 1 and zeros elsewhere.
2. For each character c of s, for j from len(t) down to 1: if c == t[j-1], add dp[j-1] to dp[j].
3. Return dp[-1].

Solution

def num_distinct(s, t):
    dp = [1] + [0]*len(t)                         # dp[j] = ways to form t[:j]; empty t: 1 way
    for c in s:
        for j in range(len(t), 0, -1):            # backwards: dp[j-1] is still the old row
            if c == t[j-1]: dp[j] += dp[j-1]      # use c as the j-th character of t
    return dp[-1]
# num_distinct("rabbbit", "rabbit") -> 3

Dry run

On s = "rabbbit", t = "rabbit", the array after each character of s (index j = 0..6):

After the third b there are 3 ways to form "rabb"; the i and t carry that through, so the answer is 3.

Complexity

• Time: O(m · n). For each of the m characters of s, scan the n + 1 positions of t.
• Space: O(n). One array the size of t.

Edge cases and pitfalls

• Empty t returns 1; t longer than s returns 0.
• Iterating j forwards double-counts: with s = "b", t = "bb" it would wrongly report 1 instead of 0.
• Counting sets of positions, not unique strings. Two choices that spell the same t from different positions both count.
• Large answers: Python handles big integers; other languages may need 64-bit or modular arithmetic for intermediate values.

Related problems

• Longest Common Subsequence (LeetCode 1143): the same skip-or-match choice, maximising length instead of counting.
• Coin Change II (LeetCode 518): counting with a 1-D array, where loop direction decides reuse.
• Partition Equal Subset Sum (LeetCode 416): another “each item used at most once” DP.