Thanks for explaining , code is simple, only understanding is the main part. It will be nice if u could explain 2 examples separately by making a full dig. from starting till all subsequences are covered. Once ex. is understood, code is doable if anyone has covered the basic. Thanks again. Tc.
def distinctSubsequences(self, s): dp=[0]*(len(s)+1) dp[0]=1 mp={} for i in range(1,len(s)+1): dp[i]=2*dp[i-1] if s[i-1] in mp: dp[i]=(dp[i]-dp[mp[s[i-1]]-1])%1000000007 mp[s[i-1]]=i return dp[len(s)]
thanks bro
Thanks for explaining , code is simple, only understanding is the main part.
It will be nice if u could explain 2 examples separately by making a full dig. from starting till all subsequences are covered. Once ex. is understood, code is doable if anyone has covered the basic.
Thanks again. Tc.
Ok thanks for the suggestions
why you subtracted dp[index-1]? as the answer is stored in in dp[index]as dp[0]=1, dp[1]=2 so you are following one based indexing
We need to ignore the subsequence that contains that character that is why index-1
it is not necessary to make us understand in english ... hindi me smjhate to aacha rehta.. aur aache se smjh me aata
Where u faced the issue ?
why ggf output is 6 and gfg is 7? both are same
Do a dry run according to algo u will understand
in string "gfg", why "ggf" and "fgg" is not a substring?
We are finding subsequences not substring
Bro by mistake I told substring while explaining
Order should be followed that's why ggf and fgg is not a subsequence
Can u tell in python
def distinctSubsequences(self, s):
dp=[0]*(len(s)+1)
dp[0]=1
mp={}
for i in range(1,len(s)+1):
dp[i]=2*dp[i-1]
if s[i-1] in mp:
dp[i]=(dp[i]-dp[mp[s[i-1]]-1])%1000000007
mp[s[i-1]]=i
return dp[len(s)]
For reference Java and python code is attached in description of video