# Distinct Subsequences Leetcode Solution In this post, you will know how to solve the Distinct Subsequences Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Leetcode by yourself. If you find any difficulty after trying several times, then you can look for solutions.

## Problem

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

A string’s subsequence is a new string formed from the original string by deleting some (can be none) of the characters without disturbing the remaining characters’ relative positions. (i.e., `"ACE"` is a subsequence of `"ABCDE"` while `"AEC"` is not).

The test cases are generated so that the answer fits on a 32-bit signed integer.

Example 1:

```Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 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 5 ways you can generate "bag" from s.
`babgbag`
`babgbag`
`babgbag`
`babgbag`
`babgbag````

Constraints:

• `1 <= s.length, t.length <= 1000`
• `s` and `t` consist of English letters.

### Distinct Subsequences Leetcode Solutions in Python

```class Solution:
def numDistinct(self, s: str, t: str) -> int:
m = len(s)
n = len(t)
dp = [ * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i] = 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]```

### Distinct SubsequencesLeetcode Solutions in CPP

```class Solution {
public:
int numDistinct(string s, string t) {
const int m = s.length();
const int n = t.length();
vector<vector<long>> dp(m + 1, vector<long>(n + 1));
for (int i = 0; i <= m; ++i)
dp[i] = 1;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
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];
}
};```

### Distinct Subsequences Leetcode Solutions in Java

```class Solution {
public int numDistinct(String s, String t) {
final int m = s.length();
final int n = t.length();
long[][] dp = new long[m + 1][n + 1];
for (int i = 0; i <= m; ++i)
dp[i] = 1;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
if (s.charAt(i - 1) == t.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
else
dp[i][j] = dp[i - 1][j];
return (int) dp[m][n];
}
}```

Note: This problem Distinct Subsequences is generated by Leetcode but the solution is provided by Brokenprogrammers. This tutorial is only for Educational and Learning purpose.