DP #3 : Count Distinct Subsequences

DP #3 Count Distinct Subsequences

Problem Statement - here

Solution - 

I am going to give the bottom-up solution for most of the DP problem series. Figuring out the top-down solution is the reader's duty. It is easy sometimes to code the top-down recurrence relation.

Coming to the problem statement, We want to find out the number of distinct subsequences. Let's create a dp array, dp[i] where dp[i] denotes the count of subsequences from index 0 to i inclusive.

So, if we know the i-1 index count of distinct subsequences, then if the s[i] is not encountered uptill now, we can simply double the dp[i-1], because to each of the dp[i-1] strings, we can generate new dp[i-1] strings by adding this character s[i]. 

But, if s[i] is already encountered for some index j < i. Then we need to consider the repetitions.

For example - "DEFABCA" we can create subsequence "DEA" using two different A, but both of them imply the same string "DEA". So,  we need to make sure that whenever we meet a character that is repeating, we subtract the count of subsequences formed in which s[j] was the last character. So, the transition becomes :

dp[i] = 2*dp[i-1] - dp[j-1] where j is the most recent index where it got repeated. 

So, basically, we are subtracting it because the dp[j-1] denotes the count of subsequences that ends at position j,  which has the same character as that of position i, so instead of ending at j, if they would have ended at index i, then it means the same thing in terms of the subsequence, so we don't need to count them twice. 

Code:

class Solution {

class Solution { public: int MOD = 1000000007; int distinctSubseqII(string s) { map<char,int> m; // Tracks last index of char int dp[s.size()+5]; dp[0] = 0; dp[1] = 1; m[s[0]] = 1; for(int i=1;i<s.size();++i){ dp[i+1] = (2*dp[i] + 1)%MOD; // + 1 because ith character alone can also

be answer. if (m[s[i]] > 0){ dp[i+1] = (dp[i+1] - dp[m[s[i]]-1] -1 + MOD)%MOD; } m[s[i]] = i+1; } return dp[s.size()]; } };