Python 3,  dp[26] x n, 76-99 ms, simple idea.
In this solution I\'m building a simple dp[26] x n to find number of all the strings between s1 and s2. At every position i from [0 to n) I decrease dp[evil[las
In this solution I\'m building a simple dp[26] x n to find number of all the strings between s1 and s2. At every position i from [0 to n) I decrease dp[evil[last_letter]] by number of evil strings that started at i-len(evil) and memorize in how many evil-string are started at i.\n\n\n```\nclass Solution:\n    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n        if s1 > s2: return 0\n        mod = 1_000_000_000 + 7\n        \n        # if s1 and s2 have common prefix that includes evil string - there will be no solution\n        # if we wouldn\'t do it - we\'ll need a lot more checks when calculate bs[]\n        for i in range(n):\n            if s1[i] != s2[i]:\n                break\n        if evil in s1[:i]:\n\t\t    return 0\n        \n        # baking first dp - for first letters\n        # dp[z] shows how many strings have z-th \n        m = len(evil)        \n        dp = [0] * 26\n        for i in range(ord(s1[0]), ord(s2[0]) + 1):\n            dp[i-ord("a")] = 1\n        #dp for bad string - bs\n        bs = [0] * m\n        if ord(s1[0]) <= ord(evil[0]) and ord(evil[0]) <= ord(s2[0]):\n            bs[0] = 1\n        # will bake future dp\'s based on prev-dp\n        prev = dp\n        # check if we have finished badString string in dp\n        if bs[m-1] > 0:\n            dp[ord(evil[-1]) - ord("a")] -= bs[m-1]     \n        \n        # calculating dp for all other letters\n        for i in range(1, n):\n            presum = (sum(prev) - 2) % mod\n\t\t\t# next letter may start from any of previous, so we take sum()\n            # but we should decrease by 2 to take care of border-case-string \n\t\t\t# if we should count them - we\'ll return them in next cycle\n            dp = [presum] * 26\n            # there are 1 string that was equal to s1[0:i) and added up into all letters\n\t\t\t# and one for s2[0:i] we excluded them in  "presum=(sum(prev)-2) % mod"\n            # now we should count it in for every letter that >=s1[i] and <=s2[i]\n            for j in range(26):\n                if ord("a") + j >= ord(s1[i]):\n                    dp[j] += 1\n                if ord("a") + j <= ord(s2[i]):\n                    dp[j] += 1\n                dp[j] = dp[j] % mod\n\n            # calculating all growing evil strings (except new one from i-th position) in reverse order\n            for j in range(1,m)[::-1]:\n                l = ord(evil[j]) - ord("a")\n                bs[j] = bs[j-1]\n                if i < j: continue\n                # if evil slided by the edge, and current symbol "slips" from it - we should decrease it by 1\n                # for the edge string that will not hold\n                if evil[:j] == s1[i-j:i] and evil[j] < s1[i]:\n                    bs[j]  -=  1\n                    bs[j] = bs[j] % mod\n                    continue\n                if evil[:j] == s2[i-j:i] and evil[j] > s2[i]:\n                    bs[j] -= 1\n                    bs[j] = bs[j] % mod\n            # check if\n            # we should do it before assigning bs[0] - new evil string startin i-th position\n            # if first char of evil-string equals last - this string should be excluded from\n            # future calculations\n            # decrease dp[evil[-1]] by bs[-1] - those are string with evel substring\n\n            l = ord(evil[-1]) - ord("a")\n            dp[l] = (dp[l] - bs[-1]) % mod\n\n            # plus there is something like a "data race" () if len(evil)==1\n            \n            l = ord(evil[0]) - ord("a")\n            if len(evil) == 1:\n\t\t\t    dp[l] = 0\n            # now start calculating new evil string rising from i-th position (should be zero if len(evil)==1)\n            bs[0] = dp[l]\n        \n            # get ready for next step\n            prev = dp            \n\n        return sum(dp) % mod\n\t\t\n\t\n```
[]