COUNT SUBSEQUENCES ques

#1

ques link: https://hack.codingblocks.com/contests/c/512/1097
code link : https://ide.codingblocks.com/s/44536

My code for the above problem has been accepted by the judge. But is it the right approach? Please guide.

#2

your approach is right. But instead of making new array for all subsequences then sorting and then removing same subsequences you can use set where subsequences will be added in sorted way and the repeated subsequence will not be added.

#3

How can we ensure that subsequences are added in a sorted way?

#4

Hey Kshitij, you can try to solve this problem using 1D DP also i.e O(N) solution.

#5

Will try. Thanks a lot for the help

#6

Can you please give a hint as to how to escape the recurring subsequences?

#7

Yes, sure… I am sharing the code snippet for the recurrence. Here, mod = (10^9)+7

     for(int i=1;i<=n;i++)
            {
              dp[i]=(2*dp[i-1])%mod;
              if(previous_count[str[i-1]]!=-1)
                dp[i]=(dp[i]-dp[previous_count[str[i-1]]-1]+mod)%mod;
            previous_count[str[i-1]]=i;
            }
#8

Will try on this approach. Thank you