Count distinct subsequence

#1

how to use dp in this problem??
i know recursive solution using a set…
plz provide code and explaination…

#2

The idea is: If all character of the string are distinct, total number of subsequences is 2^n. Now, if we find any character that have already occurred before, we should consider its last occurrence only (otherwise sequence won’t be distinct). So we have to subtract the number of subsequences due to its previous occurrence.

Let countSub(n) be count of subsequences of first n characters in input string. We can recursively write it as below.

countSub(n) = 2*Count(n-1) - Repetition

If current character, i.e., str[n-1] of str has not appeared before, then
Repetition = 0

else:
Repetition = Count(m)
Here m is index of previous occurrence of current character. We basically remove all counts ending with previous occurrence of current character.

first try at your own if not able to solve i will definitely help you

#3

why are we doing this??
We basically remove all counts ending with previous occurrence of current character.
this is what i want to understand …
i can code it on myu own…

#4

yes :+1:
try to code now

#5

Explain why We basically remove all counts ending with previous occurrence of current character.?? Then only I will be able to code it…

#6

this is neccasary to get distinct subsequences

#7

but why is that necesaary??how will i get to know that …while attempting the problem…

#8

if you don;t do this you will not get distinct subsequences
it is necessary to subtract count due to repetation

#9

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.