Distinct Subsequences

PracticeNeetCode ↗LeetCode ↗

Given two strings s and t, count the number of distinct ways t appears as a subsequence of s — characters of s chosen in order, not necessarily contiguous, that spell out t.

Example

Key Pointers

• Define dp[i][j] as the number of ways s[:i] forms t[:j] as a subsequence — building up from smaller prefixes.
• Every character of s offers a choice: skip it (contributing dp[i-1][j]), or, if it matches the current target character, also use it to match (adding dp[i-1][j-1]).
• Matching an empty t (j = 0) is always possible in exactly one way — skip everything — which seeds the whole table.

Step-by-Step Analysis

1. Build a grid sized (len(s)+1) × (len(t)+1), all zeros, with the entire first column set to 1 (dp[i][0] = 1 for every i).
2. Fill row by row, column by column, both starting at 1.
3. Each cell starts as dp[i-1][j] (skip the current character of s).
4. If s[i-1] == t[j-1], add dp[i-1][j-1] as well (use the character to match).
5. The bottom-right cell holds the total count.

Complexity

Time: O(m · n) — Space: O(m · n)

Code

def numDistinct(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):
        dp[i][0] = 1

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = dp[i - 1][j]
            if s[i - 1] == t[j - 1]:
                dp[i][j] += dp[i - 1][j - 1]

    return dp[m][n]

Code Explanation

How the solution above works, piece by piece.

1. dp[i][j] = number of ways to form t[:j] as a subsequence of s[:i].
2. dp[i][0] = 1 for every i: the empty string appears once (pick nothing).
3. Not using s[i-1] always gives dp[i-1][j] ways.
4. If s[i-1] == t[j-1], it can also be used as the last letter of t[:j]: add dp[i-1][j-1].
5. O(m × n) time and space.

Visual Walkthrough

Running it on s = "rabbbit", t = "rabbit":

Video Explanation

NeetCode — Distinct Subsequences, LeetCode 115