Similar Problems
Similar Problems not available
Distinct Subsequences  Leetcode Solution
Companies:
LeetCode: Distinct Subsequences Leetcode Solution
Difficulty: Hard
Topics: string dynamicprogramming
The Distinct Subsequences problem on LeetCode is a dynamic programming problem that asks to count the number of distinct subsequences of a string.
Problem Statement:
Given two strings s and t, return the number of distinct subsequences of s that are equal to t.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ACE" is a subsequence of "ABCDE" while "AEC" is not).
It is guaranteed the answer fits on a 32bit 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
Approach:
The problem can be solved by using dynamic programming. We can create a 2D array dp of size [n+1][m+1], where n is the length of string s and m is the length of string t. The element at dp[i][j] represents the number of distinct subsequences of s[0:i] that are equal to t[0:j].
The base conditions are:

dp[0][0] = 1, since an empty string can be matched with an empty string

dp[i][0] = 1, since an empty string can be matched with any nonempty string

dp[0][j] = 0, since a nonempty string cannot be matched with an empty string
The recurrence relation is as follows:
If s[i1] == t[j1], then we can either include or exclude the last character of s in the subsequence:
dp[i][j] = dp[i1][j] + dp[i1][j1]
Here, dp[i1][j] represents the number of times t is found in s[0:i1] and dp[i1][j1] represents the number of times t is found in s[0:i1] with the last character being s[i1].
If s[i1] != t[j1], then we can only exclude the last character of s in the subsequence:
dp[i][j] = dp[i1][j]
This is because we cannot include s[i1] in the subsequence since it does not match t[j1].
The final answer will be dp[n][m], where n and m are the lengths of s and t, respectively.
Time Complexity:
The time complexity of the solution is O(m*n), where m and n are the lengths of strings s and t, respectively.
Space Complexity:
The space complexity of the solution is O(m*n), since we are using a 2D array of size [n+1][m+1].
Code:
class Solution { public: int numDistinct(string s, string t) { int n = s.size(); int m = t.size();
vector<vector<long long>> dp(n+1, vector<long long>(m+1, 0));
for(int i=0;i<=n;i++){
dp[i][0] = 1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i1] == t[j1]){
dp[i][j] = dp[i1][j] + dp[i1][j1];
}
else{
dp[i][j] = dp[i1][j];
}
}
}
return dp[n][m];
}
};
The code is selfexplanatory and easy to understand. It returns the number of distinct subsequences of s that are equal to t.
Distinct Subsequences Solution Code
1