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 109 + 7.

&nbsp;
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".&nbsp;


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


&nbsp;
Constraints:


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


from functools import lru_cache
class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        def srange(a, b):
            return [chr(i) for i in range(ord(a),ord(b)+1)]
        def LPS(pat):
            lps = [0]
            i, target = 1, 0
            while i < len(pat):
                if pat[i] == pat[target]:
                    target += 1
                    lps.append(target)
                    i += 1
                elif target:
                    target = lps[target-1]
                else:
                    lps.append(0)
                    i += 1
            return lps
        lps = LPS(evil)
        M = 10**9+7
        @lru_cache(None)
        def dfs(i, max_matched_idx, lb, rb):
            if max_matched_idx == len(evil): return 0
            if i == n: return 1
            l = s1[i] if lb else 'a'
            r = s2[i] if rb else 'z'
            candidates = srange(l, r)
            res = 0
            for j, c in enumerate(candidates):
                nxt_matched_idx = max_matched_idx
                while evil[nxt_matched_idx] != c and nxt_matched_idx:
                    nxt_matched_idx = lps[nxt_matched_idx-1]
                res = (res + dfs(i+1, nxt_matched_idx+(c==evil[nxt_matched_idx]),
                          lb = (lb and j == 0), rb = (rb and j==len(candidates)-1)))%M
            return res
        return dfs(0, 0, True, True)
class Solution {
    Integer[][][][] dp;
    int mod = 1000000007;
    int[] lps;
    private int add(int a, int b) {
        return (a % mod + b % mod) % mod;
    }
    private int solve(char[] s1, char[] s2, int cur, boolean isStrictLower, boolean isStrictUpper, char[] evil, int evI) {
        if(evI == evil.length) return 0;
        if(cur == s2.length) return 1;
        if(dp[cur][isStrictLower ? 1 : 0][isStrictUpper ? 1 : 0][evI] != null) return dp[cur][isStrictLower ? 1 : 0][isStrictUpper ? 1 : 0][evI];
        char start = isStrictLower ? s1[cur] : 'a';
        char end = isStrictUpper ? s2[cur] : 'z';
        int res = 0;
        for(char ch = start; ch <= end; ch ++) {
            if(evil[evI] == ch)
                res = add(res, solve(s1, s2, cur + 1, isStrictLower && ch == start, isStrictUpper && ch == end, evil, evI + 1));
            else {
                int j = evI;
                while (j > 0 && evil[j] != ch) j = lps[j - 1];
                if (ch == evil[j]) j++;
                res = add(res, solve(s1, s2, cur + 1, isStrictLower && ch == start, isStrictUpper && ch == end, evil, j));
            }
        }
        return dp[cur][isStrictLower ? 1 : 0][isStrictUpper ? 1 : 0][evI] = res;
    }
    public int findGoodStrings(int n, String s1, String s2, String evil) {
        char[] arr = s1.toCharArray();
        char[] brr = s2.toCharArray();
        char[] crr = evil.toCharArray();
        lps = new int[crr.length];
        for (int i = 1, j = 0; i < crr.length; i++) {
            while (j > 0 && crr[i] != crr[j]) j = lps[j - 1];
            if (crr[i] == crr[j]) lps[i] = ++j;
        }
        dp = new Integer[n][2][2][crr.length];
        return solve(arr, brr, 0, true, true, crr, 0);
    }
}
class Solution {
public:
    using ll = long long;
    int findGoodStrings(int n, string s1, string s2, string evil) {
      int M = 1e9+7;
      int m = evil.size();
      // kmp
      int f[m];
      f[0] = 0;
      for (int i = 1, j = 0; i < m; ++i) {
        while (j != 0 && evil[i] != evil[j]) {
          j = f[j-1];
        }
        if (evil[i] == evil[j]) {
          ++j;
        }
        f[i] = j;
      }
      // next(i,c) jump function when matched i length and see c
      int next[m+1][26];
      for (int i = 0; i <= m; ++i) {
        for (int j = 0; j < 26; ++j) {
          if (i < m && evil[i] == 'a'+j) {
            next[i][j] = i+1;
          } else {
            next[i][j] = i == 0? 0: next[f[i-1]][j];
          }
        }
      }
      // dp(i,j,l1,l2) length i greater than s1, less than s2;
      // match j length of evil
      // l1 true means limited for s1, l2 true means limited for s2
      ll dp[n+1][m+1][2][2];
      memset(dp, 0, sizeof(dp));
      dp[0][0][1][1] = 1;
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
          for (int c = 0; c < 26; ++c) {
            int k = next[j][c];
            char ch = 'a'+c;
            dp[i+1][k][0][0] += dp[i][j][0][0];
            if (dp[i][j][1][1]) {
              if (ch > s1[i] && ch < s2[i]) {
                dp[i+1][k][0][0] += dp[i][j][1][1];
              } else if (ch == s1[i] && ch == s2[i]) {
                dp[i+1][k][1][1] += dp[i][j][1][1];
              } else if (ch == s1[i]) {
                dp[i+1][k][1][0] += dp[i][j][1][1];
              } else if (ch == s2[i]) {
                dp[i+1][k][0][1] += dp[i][j][1][1];
              }
            }
            if (dp[i][j][1][0]) {
              if (ch > s1[i]) {
                dp[i+1][k][0][0] += dp[i][j][1][0];
              } else if (ch == s1[i]) {
                dp[i+1][k][1][0] += dp[i][j][1][0];
              }
            }
            if (dp[i][j][0][1]) {
              if (ch < s2[i]) {
                dp[i+1][k][0][0] += dp[i][j][0][1];
              } else if (ch == s2[i]) {
                dp[i+1][k][0][1] += dp[i][j][0][1];
              }
            }
            dp[i+1][k][0][0] %= M;
          }
        }
      }
      ll ans = 0;
      for (int i = 0; i < m; ++i) {
        ans += dp[n][i][0][0] + dp[n][i][0][1] + dp[n][i][1][0];
        ans %= M;
      }
      return ans;
    }
};
const mod = 10 ** 9 + 7

let cache = null

/**
 * @param {number} n
 * @param {string} s1
 * @param {string} s2
 * @param {string} evil
 * @return {number}
 */
var findGoodStrings = function(n, s1, s2, evil) {
    /**
     * 17 bits
     * - 9 bit: 2 ** 9 > 500 by evil
     * - 6 bit: 2 ** 6 > 50 by evil
     * - 1 bit left (bound)
     * - 1 bit right (bound)
     *
     * cache: `mainTraver` is the prefix length, `evilMatch` is matching for evil
     *
     * answer: marnTravel 0, evil 0, s prefix has the last character
     */
    cache = new Array(1 << 17).fill(-1)
    return dfs(0, 0, n, s1, s2, evil, true, true, computeNext(evil))
}
/**
 * DFS:
 * 1. loop from `s1` to `s2`, range of position `i` is [0, n]: 0 means no start, n means complete
 * 2. if `s1` has traversed to nth, it means has been generated a legal character, and return 1; else
 * 3. `mainTravel` is the length of the `s` generated by dfs last time
 * 4. `evilMatch` is the length that matches the last generated `s` in evilMatch evil
 * 5. n, s1, s2, evil, left, right, next
 */
function dfs(mainTravel, evilMatch, n, s1, s2, evil, left, right, next, ans = 0) {
    // same length means that the match has been successful
    if(evilMatch === evil.length) {
        return 0
    }
    // this means s is conformed
    if(mainTravel === n) {
        return 1
    }
    
    // get key for cache
    let key = generateKey(mainTravel, evilMatch, left, right)
    // because any combination of the four categories will only appear once, there will be no repetition
    if(cache[key] !== -1) {
        return cache[key]
    }
    
    // get start, end calculate
    let [start, end] = [left ? s1.charCodeAt(mainTravel) : 97, right ? s2.charCodeAt(mainTravel) : 122]
    
    // loop
    for(let i = start; i <= end; i++) {
        // get char code
        let code = String.fromCharCode(i)
        // actually, `evilMatch` will only get longer or stay the same, not shorter
        let m = evilMatch
        
        while((m > 0) && (evil[m] !== code)) {
            m = next[m - 1]
        }

        if(evil[m] === code) {
            m++
        }

        // recursive
        ans += dfs(mainTravel + 1, m, n, s1, s2, evil, left && (i === start), right && (i === end), next)
        
        // too large
        ans %= mod
    }

    // result after cache set
    return cache[key] = ans, ans
}

// create key for cache
function generateKey(mainTravel, evilMatch, left, right) {
    return (mainTravel << 8) | (evilMatch << 2) | ((left ? 1 : 0 ) << 1) | (right ? 1 : 0)
}

// for next right move, index + 1
function computeNext(evil, n = evil.length, ans = new Array(n).fill(0), k = 0) {
    for(let i = 1; i < n; i++) {
        while((k > 0) && (evil[i] !== evil[k])) {
            k = ans[k - 1]
        }

        if(evil[i] === evil[k]) {
            ans[i] = ++k
        }
    }
    return ans
}
Find All Good Strings