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 and t consist of English letters.

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)