Distinct Subsequences
Problem Statement
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
andt
consist of English letters.
Recommended Time and Space Complexity
You should aim for a solution with O(m * n) time and O(n) space, where m is the length of string s
and n is the length of string t
.
Hint 1
Think about how the number of distinct subsequences can be built up from smaller subproblems.
Hint 2
Consider using dynamic programming to store the number of distinct subsequences for different prefixes of s
and t
.
Hint 3
The number of distinct subsequences of s[i:]
that match t[j:]
can be calculated based on whether s[i]
matches t[j]
.
Solution
Recursion
def num_distinct(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 complexity: O(2 ^ m) Space complexity: O(m)
Dynamic Programming (Top-Down)
def num_distinct(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 complexity: O(m * n) Space complexity: O(m * n)
Dynamic Programming (Bottom-Up)
def num_distinct(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 complexity: O(m * n) Space complexity: O(m * n)
Dynamic Programming (Space Optimized)
def num_distinct(s: str, t: str) -> int: m, n = len(s), len(t) dp = [0] * (n + 1) next_dp = [0] * (n + 1)
dp[n] = next_dp[n] = 1 for i in range(m - 1, -1, -1): for j in range(n - 1, -1, -1): next_dp[j] = dp[j] if s[i] == t[j]: next_dp[j] += dp[j + 1] dp = next_dp[:]
return dp[0]
Time complexity: O(m * n) Space complexity: O(n)
Dynamic Programming (Optimal)
def num_distinct(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 complexity: O(m * n) Space complexity: O(n)