Distinct Subsequences

HardDynamic Programming (1-D & 2-D)NeetCode 150SeniorOpen on LeetCodeUpdated Nov 11, 2026

You're given two strings s and t. Return the number of distinct subsequences of s that equal t. A subsequence keeps some characters of s in their original order and deletes the rest. Two subsequences count as different when they use different index positions, even if they spell the same string. The answer fits in a 32-bit signed integer.

Examples

s = "aabb", t = "ab" returns 4

Either of the two a's can pair with either of the two b's after it, giving 2 * 2 = 4.

s = "catcat", t = "cat" returns 4

The index choices are (0, 1, 2), (0, 1, 5), (0, 4, 5), and (3, 4, 5).

s = "abc", t = "abcd" returns 0

t is longer than s, so no subsequence of s can match it.

Constraints

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

Hints

Hint 1

At each character of s, you either use it to match the next character of t or skip it. What does each choice leave to solve?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Let dp[i][j] be the number of ways to form the first j characters of t from the first i characters of s. Every prefix of s forms the empty prefix of t exactly once, so dp[i][0] = 1, and dp[0][j] = 0 for j > 0. For the other cells you can always skip s[i - 1], which gives dp[i - 1][j] ways, and when s[i - 1] == t[j - 1] you can also match them, which adds dp[i - 1][j - 1]. The answer is dp[m][n]. Each row reads only the row above, so one array, filled with j running from n down to 1, replaces the table. O(m * n) time and O(n) space.

Time

O(m * n)

Space

O(n)

Pitfall

Filling the one-row array from left to right. dp[j - 1] has already been updated for the current character by then, so one character of s gets matched twice. Run j from n down to 1.

Solutions

class Solution {
    public int numDistinct(String s, String t) {
        int n = t.length();
        // int addition wraps modulo 2^32, so the final count is exact
        // whenever it fits in an int, even if an intermediate one doesn't.
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            for (int j = n; j >= 1; j--) {
                if (c == t.charAt(j - 1)) dp[j] += dp[j - 1];
            }
        }
        return dp[n];
    }
}

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