Find All Good Strings.js

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
}