...
class Solution {
public:
long int dp[501][51][2];
const long int hell=1000000007;
long int helper(string &s,int st,bool flag,string s2,int p){
if(p>=s2.length())
return 0;
if(st>=s.length())
return 1;
if(dp[st][p][flag]!=-1)
return dp[st][p][flag];
long int ans=0,np;
for(char c='a';c<='z';c++){
np=c==s2[p]?p+1:0;
if(st==0){
if(c>s[st])
break;
if(c==s[st])
ans+=helper(s,st+1,true,s2,np);
else
ans+=helper(s,st+1,false,s2,np);
}
else{
if(flag){
if(c>s[st])
break;
else if(c==s[st])
ans+=helper(s,st+1,flag,s2,np);
else
ans+=helper(s,st+1,false,s2,np);
}
else
ans+=helper(s,st+1,false,s2,np);
}
ans%=hell;
}
return dp[st][p][flag]=ans;
}
int findGoodStrings(int n, string s1, string s2, string evil) {
if(s1>s2)
return 0;
long int ans1,ans2;
memset(dp,-1,sizeof dp);
ans2=helper(s2,0,false,evil,0);
memset(dp,-1,sizeof dp);
ans1=helper(s1,0,false,evil,0);
long int c=0;
if(s1.find(evil)==string :: npos)
c=1;
//cout<<ans2<<" "<<ans1<<" "<<ans2-ans1;
return (ans2-ans1+c+hell)%hell;
}
};