Given the strings s1 and s2 of size n, and the string evil. Return the number of good strings.
A good string has size n, it is alphabetically greater than or equal to s1, it is alphabetically smaller than or equal to s2, and it does not contain the string evil as a substring. Since the answer can be a huge number, return this modulo 10^9 + 7.
 
Example 1:
Input: n = 2, s1 = "aa", s2 = "da", evil = "b"
Output: 51 
Explanation: There are 25 good strings starting with 'a': "aa","ac","ad",...,"az". Then there are 25 good strings starting with 'c': "ca","cc","cd",...,"cz" and finally there is one good string starting with 'd': "da". 

Example 2:
Input: n = 8, s1 = "leetcode", s2 = "leetgoes", evil = "leet"
Output: 0 
Explanation: All strings greater than or equal to s1 and smaller than or equal to s2 start with the prefix "leet", therefore, there is not any good string.

Example 3:
Input: n = 2, s1 = "gx", s2 = "gz", evil = "x"
Output: 2

 
Constraints:

s1.length == n
s2.length == n
s1 <= s2
1 <= n <= 500
1 <= evil.length <= 50
All strings consist of lowercase English letters.

Difficulty: interview

Starter code:

class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        

Solutions:
from functools import lru_cache

def failure(pat):
    i, target, n = 1, 0, len(pat)
    res = [0]
    while i < n:
        if pat[i] == pat[target]:
            target += 1
            res.append(target)
            i+=1
        elif target:
            target = res[target-1]
        else:
            res.append(0)
            i += 1
    return res
        
    
class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        f = failure(evil)
        @lru_cache(None)
        def dfs(idx, max_matched=0, lb=True, rb=True):
            
            if max_matched == len(evil): return 0
            if idx == n: return 1
            
            l = s1[idx] if lb else 'a'
            r = s2[idx] if rb else 'z'
                
            candidates = [chr(i) for i in range(ord(l), ord(r) + 1)]
            
            res = 0
            for i, c in enumerate(candidates):
                next_matched = max_matched
                while next_matched and evil[next_matched]!= c:
                    next_matched = f[next_matched-1]
                res += dfs(idx+1, next_matched + (evil[next_matched] == c), 
                          (lb and i==0), (rb and i == (len(candidates) - 1)))
            return res
            
        return dfs(0) % (10**9 + 7)

class Solution:
    def findGoodStrings(self, N, *args) :
        from functools import lru_cache
        s1,s2, evil = [list(map(ord, i)) for i in args]
        mod = 10 ** 9 + 7
        
        def kmp(l, c):
            while l and evil[l] != c: l = f[l-1]
            if evil[l] == c : l += 1
            return l
        
        f = [0] * len(evil) 
        for i in range(1, len(evil)):
            f[i] = kmp(f[i-1], evil[i])
        
        @lru_cache(None)
        def dp(i = 0, lcp = 0 , f1 = False, f2 = False):
            if lcp == len(evil): return 0 
            if i == N : return 1
            ans = 0
            for char in range(f1 and 97 or s1[i], f2 and 123 or s2[i]+1):
                ans += dp(i+1, kmp(lcp, char ), f1 or char > s1[i], f2 or char < s2[i])
                ans %= mod 
            return ans 

        return dp()

from functools import lru_cache

def failure(pat):
    i, target, n = 1, 0, len(pat)
    res = [0]
    while i < n:
        if pat[target] == pat[i]:
            target+= 1
            res.append(target)
            i += 1
        elif target:
            target = res[target-1]
        else:
            res.append(0)
            i += 1
    return res

class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        f = failure(evil)
        @lru_cache(None)
        def dfs(idx, max_matched=0, lb=True, rb=True):
            if max_matched == len(evil): return 0
            if idx == n: return 1
            
            l = s1[idx] if lb else 'a'
            r = s2[idx] if rb else 'z'
            
            candidates = [chr(i) for i in range(ord(l), ord(r) + 1)]
            
            res = 0
            for i, c in enumerate(candidates):
                next_match = max_matched
                while next_match and evil[next_match] != c:
                    next_match = f[next_match-1]
                res += dfs(idx+1, next_match + (c == evil[next_match]), 
                          (lb and i == 0), (rb and i == ((len(candidates) -1))))
            return res
                    
                
        return dfs(0) % (10**9 + 7)

class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        
        @lru_cache(None)
        def dfs(k, j, b1, b2):
            
            if k==n:
                return 1
            
            start = ord(s1[k]) if b1 else ord('a')
            end = ord(s2[k]) if b2 else ord('z')
            
            res = 0
            
            for x in range(start, end+1):
                
                c = chr(x)
                
                l = j
                
                while l>0 and c!=evil[l]:
                    l = lps[l-1]
                
                nevil = True
                if c==evil[l]: # here
                    l+=1
                    if l==m:
                        nevil = False
                        
                if nevil:
                    res += dfs(k+1, l, b1 and c==s1[k] ,  b2 and c==s2[k])
                    res %= mod
            
            return res
                
                
    
        m = len(evil)
        
        lps = [0]*m
        
        
        for i in range(1, m):
            
            j = lps[i-1]
            
            while j>0 and evil[j]!=evil[i]:
                j = lps[j-1]
            
            if evil[j]==evil[i]:   #here
                lps[i] = j+1
        
        mod = 10**9+7
        
        return dfs(0, 0, True, True)
        


from functools import lru_cache

        
def failure(pat):
    i, target, n = 1, 0, len(pat)
    res = [0]
    while i < n:
        if pat[target] == pat[i]:
            target += 1
            res.append(target)
            i+=1
        elif target:
            target = res[target - 1]
        else:
            res.append(0)
            i += 1
    return res
            
    
class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        f = failure(evil)
        @lru_cache(None)
        def dfs(idx, max_matched=0, lb=True, rb=True):
            if max_matched == len(evil): return 0
            if idx == n: return 1
            
            l = s1[idx] if lb else 'a'
            r = s2[idx] if rb else 'z'
            candidates = [chr(i) for i in range(ord(l), ord(r)+1)]
            
            res = 0
            for i, c in enumerate(candidates):
                next_match = max_matched
                while next_match and evil[next_match]!=c:
                    next_match = f[next_match-1]
                res += dfs(idx+1, next_match + (c == evil[next_match]), 
                          (lb and i == 0), (rb and i==(len(candidates)-1)))
            return res
        return dfs(0) % (10**9 + 7)

class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        M = 10**9 + 7
        
        table = [-1]
        pos, cnd = 1, 0
        while pos < len(evil):
            if evil[pos] == evil[cnd]:
                table.append(table[cnd])
            else:
                table.append(cnd)
                cnd = table[cnd]
                while cnd >= 0 and evil[pos] != evil[cnd]:
                    cnd = table[cnd]
            pos += 1
            cnd += 1
        table.append(cnd)
        
        @lru_cache(None)
        def dfs(i, j, u, b):
            if j == len(evil):
                return 0
            if i == n:
                return 1
            r = 0
            for c in range(ord(s1[i]) if b else 97, ord(s2[i])+1 if u else 123):
                if c == ord(evil[j]):
                    t = dfs(i+1, j+1, u and c == ord(s2[i]), b and c == ord(s1[i]))
                else:
                    p = j
                    while p >= 0:
                        if c == ord(evil[p]):
                            break
                        p = table[p]
                    t = dfs(i+1, p+1, u and c == ord(s2[i]), b and c == ord(s1[i]))
                r += t
            return r % M
        
        return dfs(0, 0, True, True)

class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        M = 10**9 + 7
        
        table = [-1]
        pos, cnd = 1, 0
        while pos < len(evil):
            if evil[pos] == evil[cnd]:
                table.append(table[cnd])
            else:
                table.append(cnd)
                cnd = table[cnd]
                while cnd >= 0 and evil[pos] != evil[cnd]:
                    cnd = table[cnd]
            pos += 1
            cnd += 1
        table.append(cnd)
        
        @lru_cache(None)
        def dfs(i, j, u, b):
            if j == len(evil):
                return 0
            if i == n:
                return 1
            r = 0
            for c in range(ord(s1[i]) if b else 97, ord(s2[i])+1 if u else 123):
                if c == ord(evil[j]):
                    t = dfs(i+1, j+1, u and c == ord(s2[i]), b and c == ord(s1[i]))
                else:
                    p = j
                    while p >= 0:
                        if ord(evil[p]) == c:
                            break
                        p = table[p]
                    t = dfs(i+1, p+1, u and c == ord(s2[i]), b and c == ord(s1[i]))
                r += t
            return r % M
        
        return dfs(0, 0, True, True)

from functools import lru_cache

def failure(pat):
    i, target, n = 1, 0, len(pat)
    res = [0]
    while i < n: 
        if pat[i] == pat[target]:
            target += 1
            res.append(target)
            i += 1
        elif target:
            target = res[target-1]
        else:
            res.append(0)
            i += 1
    return res

def srange(a, b):
    yield from (chr(i) for i in range(ord(a), ord(b)+1))
    
class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        f = failure(evil)
        @lru_cache(None)
        def dfs(idx, max_matched=0, lb=True, rb=True):
            
            if max_matched == len(evil): return 0
            if idx == n: return 1
            
            l = s1[idx] if lb else 'a'
            r = s2[idx] if rb else 'z'
            
            candidates = [*srange(l, r)]
            
            res = 0
            for i, c in enumerate(candidates):
                next_matched = max_matched
                while next_matched and evil[next_matched] != c:
                    next_matched = f[next_matched-1]
                res += dfs(idx+1, next_matched + (evil[next_matched] == c),
                          (lb and i == 0), (rb and i == (len(candidates) - 1)))
            return res
                
            
            
        return dfs(0) % (10**9 + 7)

from functools import lru_cache

def failure(pat):
    i, target, n = 1, 0, len(pat)
    res = [0]
    while i < n:
        if pat[i] == pat[target]:
            target+=1
            res.append(target)
            i += 1
        elif target:
            target = res[target-1]
        else:
            res.append(0)
            i+=1
    return res
            
def srange(a, b):
    return (chr(i) for i in range(ord(a), ord(b) + 1))

class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        f = failure(evil)
        @lru_cache(None)
        def dfs(idx, max_matched=0, lb=True, rb=True):
            
            if max_matched == len(evil): return 0
            if idx == n: return 1
            
            l = s1[idx] if lb else 'a'
            r = s2[idx] if rb else 'z'
            candidates = [*srange(l, r)]
            
            res = 0
            for i, c in enumerate(candidates):
                next_match = max_matched 
                while next_match and evil[next_match] != c:
                    next_match = f[next_match-1]
                res += dfs(idx+1, next_match + (c == evil[next_match]), 
                          lb = (lb and i == 0), rb = (rb and i == len(candidates) -1))
            
            return res
        return dfs(0) % (10**9 + 7)

from functools import lru_cache

def srange(a, b):
    yield from (chr(i) for i in range(ord(a), ord(b)+1))
        
def failure(pat): 
    res = [0]
    i, target = 1, 0
    while i < len(pat): 
        if pat[i] == pat[target]: 
            target += 1
            res += target,
            i += 1
        elif target: 
            target = res[target-1] 
        else: 
            res += 0,
            i += 1
    return res                        

class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        f = failure(evil)
        @lru_cache(None)
        def dfs(idx, max_matched=0, lb=True, rb=True):
            '''
\t\t\tidx: current_idx_on_s1_&_s2, 
\t\t\tmax_matched: nxt_idx_to_match_on_evil, 
\t\t\tlb, rb: is_left_bound, is_right_bound
\t\t\t'''
            if max_matched == len(evil): return 0 # evil found, break
            if idx == n: return 1 # base case
            
            l = s1[idx] if lb else 'a' # valid left bound
            r = s2[idx] if rb else 'z' # valid right bound
            candidates = [*srange(l, r)]
            
            res = 0
            for i, c in enumerate(candidates):
                nxt_matched = max_matched
                while evil[nxt_matched] != c and nxt_matched:
                    nxt_matched = f[nxt_matched - 1]
                res += dfs(idx+1, nxt_matched + (c == evil[nxt_matched]), 
                           lb=(lb and i == 0), rb=(rb and i == len(candidates)-1))
            return res                
        
        return dfs(0) % (10**9 + 7)


# 1397. Find All Good Strings
class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        e_len = len(evil)
        par = [0] * e_len
        
        for i in range(1, e_len):
            j = par[i-1]
            while j and evil[i] != evil[j]:
                j = par[j-1]
            j += int(evil[i] == evil[j])
            par[i] = j
            
        mod = (10 ** 9) + 7
        @lru_cache(None)
        def rec(cur, ei, sm, bg):
            if ei == e_len:
                return 0
            if cur == n:
                return 1
            
            ans = 0
            st = ord('a') if bg else ord(s1[cur])
            ed = ord('z') if sm else ord(s2[cur])
                
            for i in range(st, ed + 1):
                if i == ord(evil[ei]):
                    new_ei = ei + 1
                else:
                    new_ei = ei
                    while new_ei and evil[new_ei] != chr(i):
                        new_ei = par[new_ei - 1]
                    if evil[new_ei] == chr(i):
                        new_ei += 1
                ans += rec(cur+1, new_ei, sm | (i < ord(s2[cur])), bg | (i > ord(s1[cur])))
                
            return ans%mod
        
        return rec(0, 0, False, False)%mod

from functools import lru_cache

def srange(a, b):
    yield from (chr(i) for i in range(ord(a), ord(b)+1))
        
def failure(pat): 
    res = [0]
    i, target = 1, 0
    while i < len(pat): 
        if pat[i] == pat[target]: 
            target += 1
            res += target,
            i += 1
        elif target: 
            target = res[target-1] 
        else: 
            res += 0,
            i += 1
    return res                        

class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        f = failure(evil)
        @lru_cache(None)
        def dfs(idx, max_matched=0, lb=True, rb=True):
            '''
\t\t\tidx: current_idx_on_s1_&_s2, 
\t\t\tmax_matched: nxt_idx_to_match_on_evil, 
\t\t\tlb, rb: is_left_bound, is_right_bound
\t\t\t'''
            if max_matched == len(evil): return 0 # evil found, break
            if idx == n: return 1 # base case
            
            l = s1[idx] if lb else 'a' # valid left bound
            r = s2[idx] if rb else 'z' # valid right bound
            candidates = [*srange(l, r)]
            
            res = 0
            for i, c in enumerate(candidates):
                nxt_matched = max_matched
                while evil[nxt_matched] != c and nxt_matched:
                    nxt_matched = f[nxt_matched - 1]
                res += dfs(idx+1, nxt_matched + (c == evil[nxt_matched]), 
                           lb=(lb and i == 0), rb=(rb and i == len(candidates)-1))
            return res                
        
        return dfs(0) % (10**9 + 7)

from functools import lru_cache

def failure(pat):
    i, target, n = 1, 0, len(pat)
    res =[0]
    while i < n:
        if pat[i] == pat[target]:
            target += 1
            res += target,
            i += 1
        elif target:
            target = res[target-1]
        else:
            res += 0,
            i += 1
    return res

def srange(a, b):
    yield from (chr(i) for i in range(ord(a), ord(b)+1))


class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        f = failure(evil)
        
        @lru_cache(None)
        def dfs(idx, max_matched=0, lb=True, rb=True):
            if max_matched == len(evil): return 0
            if idx == n: return 1
            
            l = s1[idx] if lb else 'a'
            r = s2[idx] if rb else 'z'
            candidates = [*srange(l,r)]
            
            res = 0
            for i, c in enumerate(candidates):
                next_matched = max_matched
                while next_matched and evil[next_matched] != c:
                    next_matched = f[next_matched-1]
                res += dfs(idx+1, next_matched + (c == evil[next_matched]), 
                           lb=(lb and i==0), rb=(rb and i==len(candidates) - 1))
            return res
            
        return dfs(0) % (10**9 + 7)

def srange(a, b):
    yield from (chr(i) for i in range(ord(a), ord(b)+1))
        
def failure(pat): 
    res = [0]
    i, target = 1, 0
    while i < len(pat): 
        if pat[i] == pat[target]: 
            target += 1
            res += target,
            i += 1
        elif target: 
            target = res[target-1] 
        else: 
            res += 0,
            i += 1
    return res                        

class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        f = failure(evil)
        @lru_cache(None)
        def dfs(idx, max_matched=0, lb=True, rb=True):
            '''
\t\t\tidx: current_idx_on_s1_&_s2, 
\t\t\tmax_matched: nxt_idx_to_match_on_evil, 
\t\t\tlb, rb: is_left_bound, is_right_bound
\t\t\t'''
            if max_matched == len(evil): return 0 # evil found, break
            if idx == n: return 1 # base case
            
            l = s1[idx] if lb else 'a' # valid left bound
            r = s2[idx] if rb else 'z' # valid right bound
            candidates = [*srange(l, r)]
            
            res = 0
            for i, c in enumerate(candidates):
                nxt_matched = max_matched
                while evil[nxt_matched] != c and nxt_matched:
                    nxt_matched = f[nxt_matched - 1]
                res += dfs(idx+1, nxt_matched + (c == evil[nxt_matched]), 
                           lb=(lb and i == 0), rb=(rb and i == len(candidates)-1))
            return res                
        
        return dfs(0) % (10**9 + 7)


from functools import lru_cache

def failure(pat):
    i, target, n = 1, 0, len(pat)
    res = [0]
    while i < n:
        if pat[i] == pat[target]:
            target+=1
            res.append(target)
            i += 1
        elif target:
            target = res[target-1]
        else:
            res.append(0)
            i+=1
    return res
            
def srange(a, b):
    yield from (chr(i) for i in range(ord(a), ord(b) + 1))

class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        f = failure(evil)
        @lru_cache(None)
        def dfs(idx, max_matched=0, lb=True, rb=True):
            
            if max_matched == len(evil): return 0
            if idx == n: return 1
            
            l = s1[idx] if lb else 'a'
            r = s2[idx] if rb else 'z'
            candidates = [*srange(l, r)]
            
            res = 0
            for i, c in enumerate(candidates):
                next_match = max_matched 
                while next_match and evil[next_match] != c:
                    next_match = f[next_match-1]
                res += dfs(idx+1, next_match + (c == evil[next_match]), 
                          lb = (lb and i == 0), rb = (rb and i == len(candidates) -1))
            
            return res
        return dfs(0) % (10**9 + 7)

# 1397. Find All Good Strings
class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        e_len = len(evil)
        par = [0] * e_len
        
        for i in range(1, e_len):
            j = par[i-1]
            while j and evil[i] != evil[j]:
                j = par[j-1]
            j += int(evil[i] == evil[j])
            par[i] = j
            
        mod = (10 ** 9) + 7
        @lru_cache(None)
        def rec(cur, ei, sm, bg):
            if ei == e_len:
                return 0
            if cur == n:
                return 1
            
            ans = 0
            st = ord('a') if bg else ord(s1[cur])
            ed = ord('z') if sm else ord(s2[cur])
                
            for i in range(st, ed + 1):
                if i == ord(evil[ei]):
                    new_ei = ei + 1
                else:
                    new_ei = ei
                    while new_ei and evil[new_ei] != chr(i):
                        new_ei = par[new_ei - 1]
                    if evil[new_ei] == chr(i):
                        new_ei += 1
                ans += rec(cur+1, new_ei, sm | (i < ord(s2[cur])), bg | (i > ord(s1[cur])))
                if ans >= mod:
                    ans -= mod
            return ans
        
        return rec(0, 0, False, False)%mod

from functools import lru_cache
from itertools import takewhile


class Solution:
    def findGoodStrings(self, n: int, A: str, B: str, evil: str) -> int:
        MOD = 10 ** 9 + 7

        evil_checker = KMPTable(evil)

        @lru_cache(None)
        def DP(i=0, startswith_A=True, startswith_B=True, match_evil=0):
            # # <= s and not startwsith evil[e:]
            if match_evil == len(evil):
                return 0
            if i == n:
                return 1

            start = A[i] if startswith_A else 'a'
            end = B[i] if startswith_B else 'z'

            return sum(
                DP(
                    i + 1,
                    startswith_A and c == A[i],
                    startswith_B and c == B[i],
                    match_evil=evil_checker.match(c, idx=match_evil),
                )
                for c in map(chr, list(range(ord(start), ord(end) + 1)))
            ) % MOD

        return DP()


class KMPTable:
    
    def __init__(self, s):
        self.s = s
        self._init_table()
        
    def _init_table(self):
        self.table = [0, 0]
        for i in range(1, len(self.s)):
            self.table.append(
                self.match(self.s[i], idx=self.table[-1]),
            )

    def match(self, c, idx):
        if c == self.s[idx]:
            return idx + 1
        return self.match(c, self.table[idx]) if idx > 0 else 0


class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        MOD = 1000000000 + 7
        K = len(evil)
        umap = [[[[0 for x in range(2)] for j in range(2)] for k in range(K)] for l in range(n)]
        lps = list()
        def computeLPS(s: str) -> List[int]:
            N = len(s)
            dp = [0 for i in range(N)]
            
            j = 0
            for i in range(1, N):
                while j > 0 and s[i] != s[j]:
                    j = dp[j-1]
                if s[i] == s[j]:
                    j += 1
                dp[i] = j
            return dp
        
        def dfs(sp, ep, leftB, rightB) -> int:
            if ep >= K:
                return 0
            if sp >= n:
                return 1
            
            if umap[sp][ep][leftB][rightB] == 0:
                i = s1[sp] if leftB == 1 else 'a'
                j = s2[sp] if rightB == 1 else 'z'
                
                while ord(i) <= ord(j):
                    nxt = ep
                    while nxt > 0 and i != evil[nxt]:
                        nxt = lps[nxt-1]
                    
                    res = umap[sp][ep][leftB][rightB] + dfs(sp+1, (nxt+1 if evil[nxt]==i else 0), (1 if (leftB==1 and i == s1[sp]) else 0), (1 if (rightB==1 and i == s2[sp]) else 0))
                    umap[sp][ep][leftB][rightB] = res % MOD
                    i = chr(ord(i)+1)
            return umap[sp][ep][leftB][rightB]
        
        lps = computeLPS(evil)
        return dfs(0, 0, 1, 1)


import functools


class Solution:
  def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
    def calc(k, char):
      i = 0

      while i <= k and not evil[i:k] + char == evil[:k - i + 1]:
        i += 1

      return k - i + 1

    @functools.lru_cache(None)
    def dp(i, k, limit_low, limit_high):
      if k == len(evil):
        return 0
      if i == n:
        return 1

      ans = 0

      min_char = s1[i] if limit_low else 'a'
      max_char = s2[i] if limit_high else 'z'

      for o in range(ord(min_char), ord(max_char) + 1):
        curr = chr(o)

        if curr == evil[k]:
          ans += dp(i + 1, k + 1, limit_low and curr == min_char, limit_high and curr == max_char)
        else:
          ans += dp(i + 1, calc(k, curr), limit_low and curr == min_char, limit_high and curr == max_char)

      return ans % (10 ** 9 + 7)

    return dp(0, 0, True, True) % (10 ** 9 + 7)