Count Distinct Subsequences#

Levels: level-5

Data structures: string, array

Patterns: dynamic-programming

Practice#

LeetCode

Description#

Given two strings s and t, return the number of distinct subsequences of s that equal t.
A subsequence is formed by deleting zero or more characters from s without changing the order of the remaining characters.
Return the count (an integer).

Examples#

text

1getcount("abab", "ab") -> 3
2Explanation: choose indices (0,1), (0,3), (2,3)

text

1getcount("abb", "ab") -> 2

text

1getcount("abcd", "") -> 1

Python Solution#

 1def count_distinct_subsequences(s: str, t: str) -> int:
 2    """
 3    Count the number of distinct subsequences of s that equal t.
 4
 5    DP (1D optimization):
 6    dp[j] = number of ways to match t[:j] using processed prefix of s
 7    dp[0] = 1 (empty t matches in exactly 1 way)
 8
 9    For each char in s:
10      update dp backwards so we don't reuse the same s-char multiple times.
11
12    Time:  O(len(s) * len(t))
13    Space: O(len(t))
14    """
15    n, m = len(s), len(t)
16    if m == 0:
17        return 1
18    if n == 0:
19        return 0
20
21    dp = [0] * (m + 1)
22    dp[0] = 1
23
24    for ch in s:
25        for j in range(m - 1, -1, -1):
26            if ch == t[j]:
27                dp[j + 1] += dp[j]
28
29    return dp[m]