Count subsequence

#1

i am not able to think how to use bitmasking in this question plss help me

#2

@vikashkmr519,
If all the characters are unique the answer will be dp[i] = dp[i-1]*2 with dp [1] = 2.
If the char has occurred before dp[i] = dp[i] - dp[index of previous occurrence of char]

#3

i didn’t understood it , can you please explain it a little more ellaboratly

#4

@vikashkmr519,
If the character is unique (no prev occurrence in the string) do:
dp[length] = (dp[length - 1] *2) ;

If the char has any prev occurrence do:
dp[length] = (dp[length] - dp[prev_occ[ch] ]);

and update prev_occurrence array as:
prev_occ[ch] = i;

#5
#6

this code is not submiting, i took help from gfg …i understood what is happening here , but didnt understood why we are subtarcting with that particular index element , please explain me sir

#7

@vikashkmr519,
Very sorry for the late reply. dp[i+i] gives us the number of subsequences upto i in the string.
dp[i+1] = No. of distinct subsequences possible from S[0…i]
So that’s we return dp[n] to get the answer.
Your code is correct and should submit before that add this ans[i]%1000000007

#8

i didn’t understood the requirement of ans[i]%1000000007 and where to put this

#9

hello sir can you please help me in it

#10

@vikashkmr519,
Put that before you return your answer.

#11

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.