Why my code is giving wrong answer?

#1

Here is my code-

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

ll t,i,n;
cin>>t;
while(t–)
{
string s;
cin>>s;
n = s.size();
ll dp[n+2]={};
map <char,int> mp;
dp[0]=1;
for(i=0;i<n;i++)
{
dp[i+1]=(2*dp[i])%1000000007;

   if(mp.count(s[i])>0)
   {
       dp[i+1]-=(dp[mp[s[i]]]);
   }
   mp[s[i]]=i;
   dp[i+1]%=1000000007;
 }
 cout<<dp[n]<<endl;

}
return 0;
}

#2

Share your whole code using ide.codingblocks.com so that i can debug it.

#3
#4

Check now -> have added comments for better understanding.

#5

yes… this one gets accepted, but what was wrong with my code?? why that was throwing wrong output?

#6

It was cause of not taking modulus properly. You have to take it like this

dp[i]=(dp[i-1]%1000000007*2%1000000007)%1000000007;
dp[i]=(dp[i]-dp[last_occur[s[i-1]]]+1000000007)%1000000007;

To avoid overflow

#7

okay thanks…

#8

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.