Python DP
Inspired by awice :D\n\nReduce the problem to find good strings BELOW a string ceiling. AKA find all good strings below (\'da\') not including itself to \n\nfin
Inspired by awice :D\n\nReduce the problem to find good strings BELOW a string ceiling. AKA find all good strings below (\'da\') not including itself to \n\nfind # in between (\'da\') and (\'aa\'):\n= f(\'da\') - f(\'aa\') +1 to include \'da\' itself if it is a good string\n\nAlso there is a subroutine to check for the longest common prefix between evil and the current string, which can be optimized using KMP (not used here). The reason why DP can be applied is because we don\'t care exactly which character we add to our string in the tree as long as it does not hit the ceiling (as represented using flag, which can be seen as a branch in the tree), so only the length of i and longest prefix j matters.\n\n```\nfrom string import ascii_lowercase\n\nclass Solution:\n    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n        MOD = 10 ** 9 + 7\n        \n        # Find # of strings UNDER s that are good\n        @lru_cache(None)\n        def dp(i, j, flag, ceiling):\n            if j == len(evil):\n                return 0\n            if i == n:\n                return not flag #find strings that are under\n            \n            ans = 0\n            for c in ascii_lowercase:\n                if flag and c > ceiling[i]:\n                    break\n                \n                # find largest common prefix evil[:j2], after i is updated\n                j2 = j\n                while j2 and (c != evil[j2] or any(evil[k] != evil[j - j2 + k] for k in range(j2))):\n                    j2 -= 1\n                \n                if c == evil[j2]:\n                    j2 += 1\n                \n                ans += dp(i + 1, j2, flag and c == ceiling[i], ceiling)\n                ans %= MOD\n            \n            return ans\n            \n        \n        return (dp(0, 0, True, s2) - dp(0, 0, True, s1) + (evil not in s2)) % MOD\n```
[]