115. Distinct Subsequences - Explanation

Description

You are given two strings s and t, both consisting of english letters.

Return the number of distinct subsequences of s which are equal to t.

Example 1:

Input: s = "caaat", t = "cat"

Output: 3

Explanation: There are 3 ways you can generate "cat" from s.

(c)aa(at)
(c)a(a)a(t)
(ca)aa(t)

Example 2:

Input: s = "xxyxy", t = "xy"

Output: 5

Explanation: There are 5 ways you can generate "xy" from s.

(x)x(y)xy
(x)xyx(y)
x(x)(y)xy
x(x)yx(y)
xxy(x)(y)

Constraints:

1 <= s.length, t.length <= 1000
s and t consist of English letters.

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(m * n) time and O(m * n) space, where m is the length of the string s and n is the length of the string t.

Hint 1

Try to think in terms of recursion and visualize it as a decision tree, as we need to explore all subsequences of s. Can you determine the possible decisions at each recursion step?

Hint 2

We recursively iterate through the strings using indices i and j for s and t, respectively. At each recursion step, we can either skip the current character of s or include it in the current path if it matches the current character of t. Can you determine the base conditions for this recursive function?

Hint 3

If index j goes out of bounds, we return 1 as a valid subsequence is found. If index i goes out of bounds first, we return 0. At each recursion step, we return the sum of both paths. This approach is exponential. Can you think of a way to optimize it?

Hint 4

We can use memoization to cache the results of recursive calls and avoid redundant computations. A hash map or a 2D array can be used to store these results.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

Intuition

This problem asks how many distinct subsequences of string s are equal to string t.

A subsequence is formed by deleting some characters from s without changing the order of the remaining characters.

At every position in s, we have a choice:

skip the current character in s
use the current character, but only if it matches the current character in t

The recursive function represents:
“How many ways can we form t[j:] using characters from s[i:]?”

If we successfully match all characters of t, we have found one valid subsequence.

Algorithm

If t is longer than s, return 0 immediately since it is impossible.
Define a recursive function dfs(i, j):
- i is the current index in s
- j is the current index in t
If j reaches the end of t:
- Return 1 because a valid subsequence has been formed
If i reaches the end of s before t is finished:
- Return 0 because no valid subsequence can be formed
Always consider skipping the current character in s:
- res = dfs(i + 1, j)
If s[i] == t[j]:
- Also consider using this character to match t[j]
- Add dfs(i + 1, j + 1) to res
Return the total count res
Start the recursion from (0, 0) and return the final result

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        if len(t) > len(s):
            return 0

        def dfs(i, j):
            if j == len(t):
                return 1
            if i == len(s):
                return 0

            res = dfs(i + 1, j)
            if s[i] == t[j]:
                res += dfs(i + 1, j + 1)
            return res

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(2 ^ m)$
Space complexity: $O(m)$

Where $m$ is the length of the string $s$ .

2. Dynamic Programming (Top-Down)

Intuition

This problem asks us to count how many distinct subsequences of string s are equal to string t.

The recursive solution works by trying all possibilities, but it repeats the same subproblems many times. To make it efficient, we use top-down dynamic programming (memoization).

A state is uniquely identified by:

i: the current index in s
j: the current index in t

The recursive function answers the question:
“How many ways can we form t[j:] using characters from s[i:]?”

By storing the result for each (i, j) pair, we avoid recomputing the same state again and again.

Algorithm

If the length of t is greater than the length of s, return 0 since it is impossible to form t.
Create a memoization map dp where:
- the key is (i, j)
- the value is the number of ways to form t[j:] from s[i:]
Define a recursive function dfs(i, j):
- i represents the current position in s
- j represents the current position in t
If j reaches the end of t:
- Return 1 because a valid subsequence has been formed
If i reaches the end of s before t is fully matched:
- Return 0
If the state (i, j) is already in dp:
- Return the cached result
Always consider skipping the current character in s:
- res = dfs(i + 1, j)
If s[i] matches t[j]:
- Also consider using this character
- Add dfs(i + 1, j + 1) to res
Store res in dp[(i, j)] and return it
Start the recursion from (0, 0) and return the final result

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        if len(t) > len(s):
            return 0

        dp = {}
        def dfs(i, j):
            if j == len(t):
                return 1
            if i == len(s):
                return 0
            if (i, j) in dp:
                return dp[(i, j)]

            res = dfs(i + 1, j)
            if s[i] == t[j]:
                res += dfs(i + 1, j + 1)
            dp[(i, j)] = res
            return res

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $m$ is the length of the string $s$ and $n$ is the length of the string $t$ .

3. Dynamic Programming (Bottom-Up)

Intuition

We want to count how many distinct subsequences of string s are equal to string t.

A subsequence is formed by deleting characters from s without changing the order.
So for every character in s, we have a choice:

skip it
use it (only if it matches the current character in t)

Instead of solving this recursively, we use bottom-up dynamic programming by building answers for smaller suffixes first.

We define a DP state that answers:
“How many ways can we form t[j:] using s[i:]?”

By filling a DP table from the end of the strings toward the beginning, we ensure that all required subproblems are already solved.

Algorithm

Let m = len(s) and n = len(t).
Create a 2D DP table dp of size (m + 1) x (n + 1):
- dp[i][j] represents the number of ways to form t[j:] from s[i:]
Initialize the base case:
- For all i, set dp[i][n] = 1
- This means there is exactly one way to form an empty string t (by choosing nothing)
Fill the table from bottom to top and right to left:
For each position (i, j):
- Always consider skipping s[i]:
  - dp[i][j] = dp[i + 1][j]
- If s[i] == t[j]:
  - Also consider using s[i] to match t[j]
  - Add dp[i + 1][j + 1] to dp[i][j]
After filling the table, dp[0][0] contains the total number of distinct subsequences
Return dp[0][0]

class Solution:
    def numDistinct(self, 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][n] = 1

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

        return dp[0][0]

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $m$ is the length of the string $s$ and $n$ is the length of the string $t$ .

4. Dynamic Programming (Space Optimized)

Intuition

We want to count how many distinct subsequences of string s are equal to string t.

From the bottom-up DP approach, we know that:

dp[i][j] depends only on values from the next row (i + 1)
we never need older rows once a new row is computed

This means we can optimize space by keeping only two 1D arrays:

one representing results for i + 1
one representing results for the current i

The key idea stays the same:
At each position, we can either:

skip the current character in s
or use it if it matches the current character in t

Algorithm

Let m = len(s) and n = len(t).
Create two 1D arrays of size n + 1:
- dp represents results for the next row (i + 1)
- nextDp represents results for the current row (i)
Initialize the base case:
- Set dp[n] = 1 and nextDp[n] = 1
- There is exactly one way to form an empty t
Iterate over string s from right to left:
For each index i, iterate over string t from right to left:
- Always carry over the value from skipping s[i]:
  - nextDp[j] = dp[j]
- If s[i] == t[j]:
  - Add the number of ways from matching both characters:
    - nextDp[j] += dp[j + 1]
After finishing the row, copy nextDp into dp
After processing all characters, dp[0] contains the total number of distinct subsequences
Return dp[0]

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        dp = [0] * (n + 1)
        nextDp = [0] * (n + 1)

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

        return dp[0]

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(n)$

Where $m$ is the length of the string $s$ and $n$ is the length of the string $t$ .

5. Dynamic Programming (Optimal)

Intuition

We want to count how many distinct subsequences of s equal t.

From the classic DP idea:

dp[i][j] = number of ways to form t[j:] using s[i:]
Transition:
- always can skip s[i] -> dp[i+1][j]
- if s[i] == t[j], we can also match them -> dp[i+1][j+1]

The space-optimized version uses a 1D array where dp[j] represents the values from the "next row" (i+1).
But when updating dp[j] in-place, we still need access to the old value of dp[j+1] (which corresponds to dp[i+1][j+1]).

To solve this without an extra array, we carry that needed diagonal value using a single variable (prev), which always holds the correct "old dp[j+1]" for the current update.

Algorithm

Let m = len(s) and n = len(t).
Create a 1D array dp of size n + 1:
- dp[j] represents the number of ways to form t[j:] using the suffix of s currently being processed
Initialize the base case:
- dp[n] = 1 because there is exactly one way to form an empty t (choose nothing)
Iterate through s from right to left (from m - 1 down to 0):
- Set prev = 1 which corresponds to the diagonal value dp[i+1][n] (always 1)
For each character s[i], iterate through t from right to left (from n - 1 down to 0):
- Start with res = dp[j] (skipping s[i])
- If s[i] == t[j], add prev (matching both characters)
- Update prev to the old dp[j] before overwriting it (so it becomes the next diagonal)
- Write dp[j] = res
After processing all characters, dp[0] contains the total number of distinct subsequences of s that equal t
Return dp[0]

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        dp = [0] * (n + 1)

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

                prev = dp[j]
                dp[j] = res

        return dp[0]

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(n)$

Where $m$ is the length of the string $s$ and $n$ is the length of the string $t$ .

Common Pitfalls

Confusing Subsequence with Substring

A subsequence allows skipping characters while maintaining order, whereas a substring requires consecutive characters. This problem counts subsequences, so you must consider both skipping and using each character in s, not just sliding windows of consecutive characters.

Incorrect Base Case for Empty Target

When the target string t is fully matched (j == len(t)), the function should return 1 (one valid way found), not 0. Returning 0 here would cause all paths to report no valid subsequences.

# Wrong: Returns 0 when target is matched
if j == len(t):
    return 0

# Correct: Successfully formed one subsequence
if j == len(t):
    return 1

Forgetting to Always Include the Skip Option

At each position in s, you must always consider skipping the current character, regardless of whether it matches t[j]. A common mistake is only recursing when characters match, which misses valid subsequences that use later occurrences of the same character.

# Wrong: Only recurses on match
if s[i] == t[j]:
    return dfs(i + 1, j + 1)

# Correct: Always skip, optionally match
res = dfs(i + 1, j)  # Always include skip
if s[i] == t[j]:
    res += dfs(i + 1, j + 1)  # Add match option

Integer Overflow in Large Inputs

The number of distinct subsequences can grow exponentially. In languages with fixed-size integers, the result may overflow. Some implementations use unsigned integers or modular arithmetic to handle this, depending on the problem constraints.