Distinct Subsequences

Intuition

Let `dp[i][j]` be the number of distinct ways the first `i` characters of `s` can produce the first `j` characters of `t`. An empty target can always be formed exactly one way (delete everything), so `dp[i][0]` is always one. To decide `dp[i][j]`, look at the newest character `s[i-1]`. We can always ignore it and rely on the first `i-1` characters of `s`, contributing `dp[i-1][j]`. If that character also matches `t[j-1]`, we additionally have the option of using it to satisfy that last target character, contributing `dp[i-1][j-1]`. Summing those two choices gives every distinct selection without double counting. Because counts can grow large, we accumulate them in 64-bit integers.

Algorithm walkthrough

1. 1Create a table `dp` of size `(m+1) x (n+1)` where `m` and `n` are the lengths of `s` and `t`.
2. 2Initialize `dp[i][0] = 1` for every `i`, since the empty target is matched exactly once by deleting all characters.
3. 3Iterate `i` from 1 to `m` and `j` from 1 to `n`, filling the table row by row.
4. 4When `s[i-1]` differs from `t[j-1]`, carry over `dp[i-1][j]` because the new character cannot help match this target position.
5. 5When they match, add `dp[i-1][j-1]` (use the character) to `dp[i-1][j]` (skip it) to cover both options.
6. 6Return `dp[m][n]`, the number of ways all of `s` can build all of `t`.

Implementation

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        if n > m:
            return 0
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            dp[i][0] = 1
        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]