4.24.8 — Distinct Subsequences

LeetCode 115 · Hard

The problem

Count how many distinct subsequences of s equal t. Subsequences at different positions count separately.

s = "rabbbit", t = "rabbit"   →  3
s = "babgbag", t = "bag"      →  5

In the first example the three bs give three ways to pick the two bs that "rabbit" needs.

The pattern

Two strings, so a grid — the recognition step from 4.24.2.

Let dp[i][j] be the number of ways the first i characters of s can produce the first j characters of t.

The recurrence asks what you do with s[i-1], the character at the end of the s prefix. There are two cases, and the first one is where people go wrong.

If s[i-1] == t[j-1] you have a choice, and both options are legal:

• Use it to match t[j-1], leaving dp[i-1][j-1] ways.
• Skip it, and match t[j] from the earlier part of s instead, leaving dp[i-1][j] ways.

Both are counted, so they add:

dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

If they differ, s[i-1] is useless here, so you can only skip it:

dp[i][j] = dp[i-1][j]

The + in the match case is the whole problem. In 4.24.2 a match forced you to take the character; here it only offers the option, and counting means both branches contribute.

The base cases

dp[i][0] = 1 for every i. There is exactly one way to produce the empty string from any prefix of s — delete everything. This is the seed the whole table is built from, and setting it to 0 makes every answer 0.

dp[0][j] = 0 for j > 0. An empty s cannot produce a non-empty t.

The solution

Python

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][0] = 1                      # one way to make the empty string

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

        return dp[m][n]

TypeScript

function numDistinct(s: string, t: string): number {
  const m = s.length, n = t.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 0; i <= m; i++) dp[i][0] = 1;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      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];
}

Writing the skip case first and then adding the match case is cleaner than an if/else, because the skip is always available and the match is a bonus.

Trace

s = "babgbag", t = "bag". The table's last row builds up to 5, and the five subsequences are worth seeing:

b a b g b a g
b a . g . . .      indices 0,1,3
b a . . . . g      indices 0,1,6
b . . . . a g      indices 0,5,6
. . b . . a g      indices 2,5,6
. . . . b a g      indices 4,5,6

Each is a different set of positions, which is why they count separately.

Space optimisation

Each row reads only the row above, so one array suffices — but the direction matters:

dp = [0] * (n + 1)
dp[0] = 1

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

return dp[n]

The inner loop counts down, so that dp[j-1] still holds the previous row's value when it is read. Going forwards would use a value already updated in this row, which mixes rows and gives the wrong count.

This is the same direction rule as 4.23.12 and 4.24.4, and it appears here for the third time — whenever a rolled array reads a smaller index from the previous row, iterate downwards.

O(n) space.

Complexity

O(mn) time, O(mn) or O(n) space.

The counts can grow very large; the problem guarantees the answer fits in a 32-bit signed integer, which is worth noticing as a hint that no modular arithmetic is needed.

Where this goes next

• Longest Common Subsequence — the same grid, max instead of +, and a match is forced rather than optional. 4.24.2.
• Edit Distance — the same grid with three operations. 4.24.9.
• Is t a subsequence of s (LeetCode 392) — just whether, not how many, so two pointers do it in O(n) with no table. A good reminder that "does it exist" is often far cheaper than "how many".

What the interviewer will push on

"Why does the match case add two terms?" A matching character may be used or skipped, and both produce valid subsequences, so counting adds them.

"Why is dp[i][0] = 1?" One way to make the empty string — delete everything. Every count grows from that seed.

"Why does the rolled loop go backwards?" So dp[j-1] still holds the previous row.

"How does this differ from LCS?" LCS forces the match and takes a maximum; this offers the match and adds.

"What if you only needed to know whether t is a subsequence?" Two pointers, O(n), no DP at all.

One thing to volunteer: state the difference from LCS in one sentence before writing code. It is the same grid, and naming the one changed rule shows you are reusing a template rather than meeting a new problem.

Next: 4.24.9 Edit Distance — the most useful two-string DP there is.