Not able to understand hint

#1

the hint is very complex what is being done??

Please tell me how to approach this ques?
#2

Hey @pranjalarora98

Consider string ABCDEFG
Subsequences of size 0 : 1 which is {} empty string
dp[0] = 1;
then size 1 : dp[1] are {} , A , hence dp[1] = 2;
size 2 : dp[2] are || {}, A , B , AB hence dp[2] = 4;
size 3 : dp[3] are {},A , B , C, AB ,AC , BC, ABC hence dp[3] = 8

so we a pattern dp[i] = dp[i-1]*2;
but then we have duplicate occurance of characters in the string

Now Consider the string S=“ABCB”

Let DP[i+1] = No. of distinct subsequences possible from S[0…i]

where DP[0] = 1, for empty subsequence { }

So, for the string “ABCDEFG”

For i=0;

Possible Subsequences: { },A

DP[1] = 2;

For i=1:

Possible Subsequences: { },A,B,AB

DP[2] = 4

for i=2:

Possible Subsequences: { },A,B,AB,C,AC,BC,ABC

DP[3] = 8

As we can observe,

DP[i] = DP[i-1]*2;

But till now, all characters were distinct.

Consider the next chracter ‘B’(Getting repeated),

Possible Subsequences:

{ },A,B,AB,C,AC,BC,ABC,B,AB,BB,ABB,CB,ACB,BCB,ABCB

DP[4] = 16

But here as we can see, (B,AB) are repeating (hence the subsequences are not distinct), Which we had obtained earlier by appending B at the end to ({ },A).

Hence the No. of repeating subsequences = DP[1] in this case.

Where, 1 is nothing but the previous occurence of the characer B. And we need to subtract the no. of repeating subsequences to get the result.

In this case,

DP[4] = 16 - 2 = 14

Hence DP[i] = DP[i-1]*2 - DP[Immediate previous occurence of character S[i-1]], if S[i-1] has occurred before.

Final Algo. obtained:

DP[0] = 1;

For i=0 to length(S)-1:

DP[i+1] = DP[i]*2;

if(previous[S[i]]>=0)

DP[i+1] = DP[i+1] - DP[previous[S[i]]];

previous[S[i]] = i;

Expected Output: DP[length(S)]

Note:

Previous[i] = Index of prev. occurence of i. If there is no previous occurence of i, then I have initialized it to some negative value.

#3

Hey @pranjalarora98

for(int i=0;i<n;i++)  
        {
            long long int num=2*dp[i]%1000000007;
            if(cust[s[i]])
            num=(num-dp[cust[s[i]]-1]+1000000007)%1000000007;//updated 
            dp[i+1]=num;
            // cust[i]=s[i];
            cust[s[i]]=i+1; //i+1 here
        }

used 1 indexing for string because map default value is 0 so u wont be able to access 1st element if repeated in case u do 0 indexing in cus

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

Count subsequences problem