## Similar Problems

Similar Problems not available

# Number Of Matching Subsequences - Leetcode Solution

## Companies:

LeetCode: Number Of Matching Subsequences Leetcode Solution

Difficulty: Medium

Topics: hash-table dynamic-programming binary-search string array sorting

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.

- 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.
- 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].
- 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]).
- 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.

## Number Of Matching Subsequences Solution Code

`1`