Problem Statement:

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

A subsequence of a string is a new string generated from the original string by deleting some characters (can be none) without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".

A distinct subsequence is a subsequence that doesn't have the same sequence of characters as another subsequence.

Example 1:

Input: s = "rabbbit", t = "rabbit" Output: 3 Explanation: As shown below, there are three ways you can generate "rabbit" from S. rabbbit rabbbit rabbbit

Example 2:

Input: s = "babgbag", t = "bag" Output: 5 Explanation: As shown below, there are five ways you can generate "bag" from S. babgbag babgbag babgbag babgbag babgbag

Approach:

To solve the given problem, we’ll employ dynamic programming.

1. Let matchCount[i][j] represents the number of distinct subsequences of s[0:i] that equals to t[0:j], where s[0:i] represents from the 0th index to the ith index of string s.
2. If t[j] == s[i], then we can choose to include s[i] in our subsequence, and thus matchCount[i][j] will be the number of distinct subsequences we can get not considering s[i] PLUS the number of distinct subsequences we can get by considering s[i], which is simply matchCount[i-1][j-1].
3. If t[j] != s[i], we cannot include s[i] in our subsequence, and thus matchCount[i][j] will be the number of distinct subsequences we can get from s[0:i-1] (not considering s[i]).
4. At the end, we return matchCount[m][n] , where m and n represent the lengths of strings s and t.

Solution:

Here is the Python implementation of the above approach:

def numDistinct(s: str, t: str) -> int: m, n = len(s), len(t) matchCount = [[0] * (n + 1) for _ in range(m + 1)]

# initializing matchCount for i = 0
for j in range(n + 1):
    matchCount[0][j] = 0

# initializing matchCount for j = 0
for i in range(m + 1):
    matchCount[i][0] = 1

for i in range(1, m + 1):
    for j in range(1, n + 1):
        if s[i - 1] == t[j - 1]:
            matchCount[i][j] = matchCount[i - 1][j - 1] + matchCount[i - 1][j]
        else:
            matchCount[i][j] = matchCount[i - 1][j]

return matchCount[m][n]

Test case 1

s1 = "rabbbit" t1 = "rabbit" assert numDistinct(s1, t1) == 3

Test case 2

s2 = "babgbag" t2 = "bag" assert numDistinct(s2, t2) == 5

Test case 3

s3 = "ABCDE" t3 = "ACE" assert numDistinct(s3, t3) == 1

Test case 4

s4 = "ABCDE" t4 = "AEC" assert numDistinct(s4, t4) == 0

Time Complexity:

The time complexity of the given solution is O(m x n), where m and n represent the lengths of strings s and t. This is because we’re iterating through both strings once.

Space Complexity:

The space complexity of the given solution is O(m x n), which is the space required to store the matchCount matrix of dimensions m+1 x n+1.

1