Problem statement

Given two strings s and t, return the number of distinct subsequences of s that equal t.

Subsequences occurring at different index sets count separately.

Example 1

Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation: Any one of the three b's can be the one dropped.

Example 2

Input: s = "babgbag", t = "bag"
Output: 5

Example 3

Input: s = "abc", t = "abcd"
Output: 0

Constraints

• 1 <= s.length, t.length <= 1000
• Both consist of English letters.
• The answer fits in a 32-bit signed integer.

Hints for Distinct Subsequences

1. Hint 1

   dp[i][j] counts the ways to build t[0..j) from s[0..i).

2. Hint 2

   You may always skip s[i-1]; when it matches t[j-1] you may also consume it.

3. Hint 3

   Rolling the table down to one row works if you iterate j downwards.

How to solve Distinct Subsequences

Count matchings rather than searching for them. Each character of s either participates in the match or is skipped, and the two options add.

Approach

1. Let dp[j] be the number of ways to form t[0..j) using the prefix of s processed so far; start with dp[0] = 1.
2. For each character of s, sweep j from m down to 1.
3. When s[i-1] == t[j-1], add dp[j-1] to dp[j] — consuming this character to extend a shorter match.
4. Return dp[m].

Why it works

dp[j] before the update already counts matches that skip s[i-1], so adding dp[j-1] folds in the matches that use it. Sweeping j downwards guarantees dp[j-1] still holds the previous row's value, which is what the recurrence needs.

Complexity

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

Pitfalls

• Sweeping j upwards uses the already-updated dp[j-1] and counts the same character twice.
• dp[0] = 1 is essential: there is exactly one way to form the empty string.
• Recursing without memoisation is exponential on inputs like "babgbag" scaled up.

Reference solution

Python

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

Java

public static int numDistinct(String s, String t) {
    int m = t.length();
    long[] dp = new long[m + 1];
    dp[0] = 1;
    for (int i = 0; i < s.length(); i++) {
        for (int j = m; j >= 1; j--) {
            if (s.charAt(i) == t.charAt(j - 1)) dp[j] += dp[j - 1];
        }
    }
    return (int) dp[m];
}

C++

int numDistinct(string s, string t) {
    int m = (int) t.size();
    vector<long long> dp(m + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < (int) s.size(); i++) {
        for (int j = m; j >= 1; j--) {
            if (s[i] == t[j - 1]) dp[j] += dp[j - 1];
        }
    }
    return (int) dp[m];
}

JavaScript

var numDistinct = function(s, t) {
    const m = t.length;
    const dp = new Array(m + 1).fill(0);
    dp[0] = 1;
    for (let i = 0; i < s.length; i++) {
        for (let j = m; j >= 1; j--) {
            if (s.charAt(i) === t.charAt(j - 1)) dp[j] += dp[j - 1];
        }
    }
    return dp[m];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Prefix and Suffix Search Hard
• Recover a Tree From Preorder Traversal Hard
• Minimum Time to Revert Word to Initial State II Hard
• Maximum Product of the Length of Two Palindromic Substrings Hard
• Longest Chunked Palindrome Decomposition Hard
• K-Similar Strings Hard