Faster and less memory than all other solutions
Intuition\n Describe your first thoughts on how to solve this problem. \nThis problem requires very, very careful counting.\n\n# Approach\n Describe your approa
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis problem requires very, very careful counting.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe problem can be decomposed into two: counting all valid strings less than s1, then all valid strings less than s2 (and then considering s2 itself separately).\n\nCounting all valid strings less than some string s is straightforward, by recursion on n, if there is no excluded string. It is still easy when the excluded "evil" string has no overlapping prefixes and suffixes.\n\nWhen there is overlap, one also has to keep track of the number of valid strings that end in certain suffixes of the excluded string.\n\nFor example: if the excluded string is "bbb", one has to keep track of valid strings ending in "b" and "bb". If the excluded string is "zaaz", one has to keep track of valid strings ending in "zaa".\n\n# Complexity\n- Time complexity: The solution takes at most $O(nl^2)$ time, where $l$ is the length of the excluded "evil" string.\n\n- Space complexity: The solution uses no more than $O(n)$ memory.\n\n\n# Code\n```\nclass Solution:\n    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n        p=10**9+7\n        ord_a=ord(\'a\')\n        l=len(evil)\n        dup=[]\n        for i in range(1, l):\n            if evil[i:]==evil[:l-i]:\n                dup.append(i)\n        lend=len(dup)\n        def count(s):\n            tmp_ct=0\n            bd=1\n            ind=n\n            without_s=[]\n            for i in range(n):\n                tmp_ct*=26\n                if bd:\n                    tmp_ct+=ord(s[i])-ord_a\n                if i>=l-1 and ind>i-l and evil<s[i-l+1:i+1]:\n                    tmp_ct-=1\n                if i>=l:\n                    tmp_ct-=without_s[i-l]\n                if i>=l-1:\n                    if s[i-l+1:i+1]==evil:\n                        bd=0\n                        ind=i\n                tmp_ct%=p\n                tmp_with_s=0\n                for j in range(lend):\n                    d=dup[j]\n                    if i>=d:\n                        tmp_with_s+=without_s[i-d]\n                    if i>=d-1 and ind>i-d and evil[:d]<s[i-d+1:i+1]:\n                        tmp_with_s+=1\n                without_s.append(tmp_ct-tmp_with_s)\n            return tmp_ct, bd\n        str_ct1, bd1=count(s1)\n        str_ct2, bd2=count(s2)\n        return (str_ct2-str_ct1+bd2)%p\n        \n```
['Python3']