Count Subsequences DP

#1

Hello sir/ma’am, my code for this problem is unable to pass some of the test cases. Could you please help me figure out what’s the error?? Sharing my code: https://ide.codingblocks.com/s/215002

#2

@priyanshi.agarwal3405
Take modulo at possible positions like:-

  1. dp[i]=(2*dp[i-1])%mod;
  2. dp[i]=(dp[i]-dp[last[s[i-1]-‘A’]] + mod)%mod;
#3

@priyanshi.agarwal3405 Also please mark this doubt as resolved if you don’t have any furthur doubt and able to submit it now.

#4

What is the significance of doing " +mod " in 2nd point??

#5

As in 1) we have taken the mod, so when during 2) it is possible that dp[i] is less than do[last[s[i-1]-A]] and then the value will be negative , so just add mod because mod%mod is zero.

It is just a basic modulo property, you must have read in Number Theory or you can also just google it.
I hope this clears your doubt.

#6

Okay sir!! Thank you!!!