LeetCode 115: Distinct Subsequences

Problem Restatement

We are given two strings:

s
t

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

A subsequence is formed by deleting zero or more characters without changing the order of the remaining characters.

The official problem asks for the number of distinct subsequences of s equal to t. (leetcode.com)

For example:

s = "rabbbit"
t = "rabbit"

The answer is:

3

because there are three different ways to delete one 'b' from "rabbbit" to obtain "rabbit".

Input and Output

The function shape is:

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        ...

Examples

Consider:

s = "rabbbit"
t = "rabbit"

We need to remove exactly one 'b'.

Possible choices:

ra[b]bbit
rab[b]bit
rabb[b]it

Each produces:

rabbit

So the answer is:

3

Now consider:

s = "babgbag"
t = "bag"

Possible subsequences:

ba[g]
ba[g]bag
[b]abgag
...

The answer is:

5

For:

s = "abc"
t = "abcd"

the answer is:

0

because we cannot build a longer string from a shorter one.

First Thought: Try Every Subsequence

One brute force approach is:

1. Generate every subsequence of s.
2. Count how many equal t.

But a string of length n has:

possible subsequences.

That becomes impossible for large inputs.

We need a more structured way to count possibilities.

Key Insight

At each character in s, we have two choices:

1. Skip the character.
2. Use the character if it matches the current character in t.

Suppose:

s = "babgbag"
t = "bag"

If we are comparing:

s[i] = 'b'
t[j] = 'b'

then:

• We may use this 'b' to match t[j].
• Or skip it and try another 'b' later.

This naturally creates overlapping subproblems.

Dynamic programming helps us reuse those results.

Dynamic Programming Definition

Define:

dp[i][j]

as:

The number of ways to form t[:j] using s[:i].

That means:

• First i characters of s
• First j characters of t

Base Cases

An empty target string can always be formed:

dp[i][0] = 1

for every i.

There is exactly one way:

delete everything

A non-empty target cannot be formed from an empty source:

dp[0][j] = 0

for every positive j.

Transition

If:

s[i - 1] == t[j - 1]

then we have two choices:

1. Use this matching character.
2. Skip this character.

So:

If the characters do not match:

s[i - 1] != t[j - 1]

then we can only skip the character from s:

Algorithm

Let:

m = len(s)
n = len(t)

Create a DP table of size:

(m + 1) x (n + 1)

Initialize:

dp[i][0] = 1

Then fill the table row by row.

For each pair (i, j):

1. If characters match:
   1. Count ways using the character.
   2. Count ways skipping the character.
2. Otherwise:
   1. Only skip the character.

The final answer is:

dp[m][n]

Correctness

The DP state dp[i][j] represents the number of ways to form the first j characters of t using the first i characters of s.

If the current characters match:

s[i - 1] == t[j - 1]

then every valid subsequence falls into one of two categories:

1. Subsequences that use this matching character.
2. Subsequences that skip it.

The number of subsequences that use the character is:

dp[i - 1][j - 1]

because the earlier parts must form t[:j-1].

The number of subsequences that skip the character is:

dp[i - 1][j]

because we still need to form the same target prefix.

Adding these counts gives the total number of valid subsequences.

If the characters do not match, the current character in s cannot help form t[j-1]. Therefore, the only option is to skip it, giving:

dp[i - 1][j]

The base cases are also correct:

• An empty target has exactly one subsequence.
• A non-empty target cannot be formed from an empty source.

Thus, the DP table correctly counts all distinct subsequences.

Complexity

Here:

• m = len(s)
• n = len(t)

Implementation

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m = len(s)
        n = len(t)

        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]

Code Explanation

Get the string lengths:

m = len(s)
n = len(t)

Create the DP table:

dp = [[0] * (n + 1) for _ in range(m + 1)]

Initialize the empty-target base case:

for i in range(m + 1):
    dp[i][0] = 1

Now fill the table:

for i in range(1, m + 1):
    for j in range(1, n + 1):

If the characters match:

if s[i - 1] == t[j - 1]:

then either use or skip the character:

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

Otherwise, skip the character:

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

Finally:

return dp[m][n]

Testing

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m = len(s)
        n = len(t)

        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]

def run_tests():
    s = Solution()

    assert s.numDistinct("rabbbit", "rabbit") == 3

    assert s.numDistinct("babgbag", "bag") == 5

    assert s.numDistinct("abc", "abcd") == 0

    assert s.numDistinct("abc", "") == 1

    assert s.numDistinct("", "a") == 0

    assert s.numDistinct("aaaaa", "aa") == 10

    print("all tests passed")

run_tests()

Test meaning: