HardStringDynamic Programming

Distinct Subsequences

1 approach, code in every language

You are given two strings `s` and `t`. A subsequence of `s` is any string obtained by deleting zero or more characters from `s` without changing the order of the remaining characters.

Return the number of distinct subsequences of `s` that are exactly equal to `t`. Two selections count as different if they choose characters from different positions in `s`, even when the resulting strings look identical.

The answer is guaranteed to fit in a signed 32-bit integer.

Example 1

Input: s = "rabbbit", t = "rabbit"

Output: 3

The target `rabbit` can be formed by keeping different combinations of the three `b` characters in `rabbbit`, giving three distinct position selections.

Example 2

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

Output: 5

There are five different ways to pick positions from `babgbag` that spell out `bag`.

Constraints

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

2D Dynamic Programming

Build a table where each entry counts the ways a prefix of `s` can form a prefix of `t`, reusing shorter prefixes to fill each cell in constant time.

Loading animation…

Intuition

Let `dp[i][j]` be the number of distinct ways the first `i` characters of `s` can produce the first `j` characters of `t`. An empty target can always be formed exactly one way (delete everything), so `dp[i][0]` is always one. To decide `dp[i][j]`, look at the newest character `s[i-1]`. We can always ignore it and rely on the first `i-1` characters of `s`, contributing `dp[i-1][j]`. If that character also matches `t[j-1]`, we additionally have the option of using it to satisfy that last target character, contributing `dp[i-1][j-1]`. Summing those two choices gives every distinct selection without double counting. Because counts can grow large, we accumulate them in 64-bit integers.

Algorithm walkthrough

1Create a table `dp` of size `(m+1) x (n+1)` where `m` and `n` are the lengths of `s` and `t`.
2Initialize `dp[i][0] = 1` for every `i`, since the empty target is matched exactly once by deleting all characters.
3Iterate `i` from 1 to `m` and `j` from 1 to `n`, filling the table row by row.
4When `s[i-1]` differs from `t[j-1]`, carry over `dp[i-1][j]` because the new character cannot help match this target position.
5When they match, add `dp[i-1][j-1]` (use the character) to `dp[i-1][j]` (skip it) to cover both options.
6Return `dp[m][n]`, the number of ways all of `s` can build all of `t`.

Implementation

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        if n > m:
            return 0
        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):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j]
        return dp[m][n]

Time

O(m * n)

Space

O(m * n)

Each of the m*n table cells is computed once from previously filled neighbors. Space can be reduced to O(n) by keeping only the previous row.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Ways to Spell the Motif is our own problem on the technique behind Distinct Subsequences: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free