Question -

We are given 3 strings let say s1,s2,s3. s1 and s2 are of same length. We need to find the number of strings t of length = length of s1 or s2 (both are same) such that s1<=t<=s2 and t does not contain s3 as its substring.

My approach -

Initially, I am trying to precalculate $$$dp[i][j]$$$ as the number of strings of length n-i such that the prefix it has a prefix of length exactly j of string s3. here $$$0<=j<=len(s3)-1$$$, [Beacuse we cannot afford the original entire string as it is not allowed]. Here transitions are $$$dp[i][j]=dp[i+1][j-1]$$$, only for $$$dp[i][0]$$$ we need to place all characters and ensure it is not a suffix of $$$s3$$$.

Then I am doing normal digit dp type of thing, let's say we are at $$$i^th$$$ position in string s1, I am placing character c from s1[i]+1 to upto 'z' at $$$ith$$$ position to make it greater than s and checking for all prefix length x of s3 which can be placed at the $$$(i+1)^th$$$ position so that it do not form the original string $$$s3$$$, the only condition here is string $$$suffix(s1_{i-1},len(s3)-x-1)+char(k)+prefix(s3,x)$$$ must not be equal to $$$s3$$$. Then we can place it and add $$$dp[i+1][x]$$$ to our answer. Also at last if the original string ($$$s1$$$) satisfies this condition then add 1 to answer. Let this function be num.

Similarly do the same thing for $$$s2$$$.

Final answer is $$$num(s1)-num(s2)$$$+(s2 satisfies the condition) But it turns out that I am overcounting sometimes. Can anyone tell me if this method is incorrect or someone can suggest some better method?

It will be highly appreciated

Thanks