Distinct Subsequences

Dynamic Programming

HardLeetCode #115

35 min

Problem Statement

Given two strings s and t, return the number of distinct subsequences of s which equals t.

Example

Example 1:

s:rabbbit

t:rabbit

Distinct Subsequences:3

r a b b _ i t

r a b _ b i t

r _ a b b i t

Solution

This is another 2D dynamic programming problem. We'll create a DP grid, dp, of size (m+1) x (n+1), where m and n are the lengths of strings s and t. dp[i][j] will represent the number of distinct subsequences of s[0...i-1] which equals t[0...j-1].

The recurrence relation is as follows: If s[i-1] == t[j-1], then dp[i][j] = dp[i-1][j-1] + dp[i-1][j]. Otherwise, dp[i][j] = dp[i-1][j].

Algorithm Steps (DP)

Create a DP grid of size (m+1) x (n+1).
Initialize the first column to 1s, as an empty string is a subsequence of any string.
Iterate through the grid from (1, 1) to (m, n).
If s[i-1] == t[j-1], dp[i][j] = dp[i-1][j-1] + dp[i-1][j].
Otherwise, dp[i][j] = dp[i-1][j].
The final answer is dp[m][n].

Step: 1 / 44

Distinct Subsequences Solution


def numDistinct(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][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]