can’t understand editorial solution
char s[MAX];
int previous_count[200],hash[200];
ll dp[MAX],sum[MAX];
int main()
{
boost;cin.tie(0);cout.tie(0);
// freopen(“input4.txt”,“r”,stdin);
int n,t;cin>>t;
while(t–)
{
cin>>s;
ms(previous_count,-1);
n=strlen(s);
ms(dp,0);
dp[0]=1;
previous_count[s[0]]=0;
f(i,1,n)
{
dp[i]=(2*dp[i-1])%mod;
if(previous_count[s[i-1]]!=-1)
dp[i]=(dp[i]-dp[previous_count[s[i-1]]-1]+mod)%mod;
previous_count[s[i-1]]=i;
}
Hi @Divya_321
The editorial has simple and undertandable example ,I`ll reiterate over those examples so that the code becomes easier to understand
string ABCDEFG
Subsequences of size 0 : 1 {} empty string
dp[0] = 1;
then size 1 : dp[1] ?? \ {} , A , dp[1] = 2;
size 2 : dp[2] ?? || {}, A , B , AB dp[2] = 4;
size 3 : dp[3] ??? \ {},A , B , C, AB ,AC , BC, ABC dp[3] = 8
so we a pattern dp[i] = dp[i-1]*2;
but then we have duplicate occurance of characters in the string
here we see a case
stirng : ABCB
{},A , B , C, AB ,AC , BC, ABC , CB , BB ,__ AB__ , __ B __
those with ’ __ ’ mark are the duplicate subsequences , so we see that 2 duplicate subsequence happen
for this the editorial says we mark the position where a character has previously occured, if so we
get a formula
dp[i] = 2* dp[i-1] - dp[pos[i]];
pos[i] is the position where the character last occured.
in this case B occured at 1
do dp[1] is subtracted;
dp[4] = 2* 8 - dp[1] = 14
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.