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)