Editorial: Distinct Subsequences

by admin · Oct. 18, 2026

1 Intuition

dp[j] = ways to form the first j characters of t from the prefix of s seen so far.

2 Approach

For each character of s, update j from right to left: if it matches t[j−1], it can extend every way of forming t[:j−1].

3 Complexity Analysis

Time O(|s|·|t|), Space O(|t|).

4 Solution Code

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        dp = [1] + [0] * len(t)
        for c in s:
            for j in range(len(t), 0, -1):
                if t[j - 1] == c:
                    dp[j] += dp[j - 1]
        return dp[-1]

5 Code Walkthrough

The reference solution below implements the approach step by step.