Problem

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.

Examples

Example 1

1
2
3

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

1
2
3

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

1
2

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

Solution

Method 1 – Dynamic Programming with Automaton (KMP)

Intuition

We need to count the number of strings of length n between s1 and s2 that do not contain the substring evil. Since the evil substring can appear anywhere, we use automaton (KMP) to track the current match of evil, and DP to count valid strings for each position, prefix constraint, and evil match state.

Approach

  1. Build the KMP failure function for evil to allow efficient substring matching.
  2. Use a DP function with parameters: position, tight_low (is prefix >= s1), tight_high (is prefix <= s2), and matched (length of evil matched so far).
  3. For each position, try all possible characters (‘a’ to ‘z’) within the bounds set by s1 and s2.
  4. For each character, update the evil match state using the KMP automaton.
  5. If evil is fully matched, skip this path.
  6. Use memoization to cache results for each state.
  7. The answer is the total number of valid strings modulo 10^9+7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    int mod = 1e9+7;
    int findGoodStrings(int n, string s1, string s2, string evil) {
        vector<int> fail(evil.size(), 0);
        for (int i = 1, j = 0; i < evil.size(); ++i) {
            while (j && evil[i] != evil[j]) j = fail[j-1];
            if (evil[i] == evil[j]) fail[i] = ++j;
        }
        vector<vector<vector<vector<int>>>> dp(n+1, vector<vector<vector<int>>>(2, vector<vector<int>>(2, vector<int>(evil.size(), -1))));
        function<int(int,int,int,int)> dfs = [&](int pos, int low, int high, int match) {
            if (match == evil.size()) return 0;
            if (pos == n) return 1;
            int& ans = dp[pos][low][high][match];
            if (ans != -1) return ans;
            ans = 0;
            char from = low ? s1[pos] : 'a';
            char to = high ? s2[pos] : 'z';
            for (char c = from; c <= to; ++c) {
                int nxt = match;
                while (nxt && c != evil[nxt]) nxt = fail[nxt-1];
                if (c == evil[nxt]) ++nxt;
                ans = (ans + dfs(pos+1, low && c==from, high && c==to, nxt)) % mod;
            }
            return ans;
        };
        return dfs(0, 1, 1, 0);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

func findGoodStrings(n int, s1, s2, evil string) int {
    mod := int(1e9+7)
    fail := make([]int, len(evil))
    for i, j := 1, 0; i < len(evil); i++ {
        for j > 0 && evil[i] != evil[j] {
            j = fail[j-1]
        }
        if evil[i] == evil[j] {
            j++
        }
        fail[i] = j
    }
    memo := map[[4]int]int{}
    var dfs func(pos, low, high, match int) int
    dfs = func(pos, low, high, match int) int {
        if match == len(evil) {
            return 0
        }
        if pos == n {
            return 1
        }
        key := [4]int{pos, low, high, match}
        if v, ok := memo[key]; ok {
            return v
        }
        ans := 0
        from, to := 'a', 'z'
        if low == 1 {
            from = rune(s1[pos])
        }
        if high == 1 {
            to = rune(s2[pos])
        }
        for c := from; c <= to; c++ {
            nxt := match
            for nxt > 0 && byte(c) != evil[nxt] {
                nxt = fail[nxt-1]
            }
            if byte(c) == evil[nxt] {
                nxt++
            }
            ans = (ans + dfs(pos+1, boolToInt(low==1 && c==from), boolToInt(high==1 && c==to), nxt)) % mod
        }
        memo[key] = ans
        return ans
    }
    return dfs(0, 1, 1, 0)
}
func boolToInt(b bool) int { if b { return 1 }; return 0 }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    int mod = 1000000007;
    public int findGoodStrings(int n, String s1, String s2, String evil) {
        int[] fail = new int[evil.length()];
        for (int i = 1, j = 0; i < evil.length(); i++) {
            while (j > 0 && evil.charAt(i) != evil.charAt(j)) j = fail[j-1];
            if (evil.charAt(i) == evil.charAt(j)) fail[i] = ++j;
        }
        Integer[][][][] dp = new Integer[n+1][2][2][evil.length()];
        return dfs(0, 1, 1, 0, n, s1, s2, evil, fail, dp);
    }
    int dfs(int pos, int low, int high, int match, int n, String s1, String s2, String evil, int[] fail, Integer[][][][] dp) {
        if (match == evil.length()) return 0;
        if (pos == n) return 1;
        if (dp[pos][low][high][match] != null) return dp[pos][low][high][match];
        int ans = 0;
        char from = low==1 ? s1.charAt(pos) : 'a';
        char to = high==1 ? s2.charAt(pos) : 'z';
        for (char c = from; c <= to; c++) {
            int nxt = match;
            while (nxt > 0 && c != evil.charAt(nxt)) nxt = fail[nxt-1];
            if (c == evil.charAt(nxt)) nxt++;
            ans = (ans + dfs(pos+1, low==1&&c==from?1:0, high==1&&c==to?1:0, nxt, n, s1, s2, evil, fail, dp)) % mod;
        }
        return dp[pos][low][high][match] = ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    val mod = 1000000007
    fun findGoodStrings(n: Int, s1: String, s2: String, evil: String): Int {
        val fail = IntArray(evil.length)
        for (i in 1 until evil.length) {
            var j = fail[i-1]
            while (j > 0 && evil[i] != evil[j]) j = fail[j-1]
            if (evil[i] == evil[j]) fail[i] = j+1
        }
        val dp = Array(n+1) { Array(2) { Array(2) { Array(evil.length) { -1 } } } }
        fun dfs(pos: Int, low: Int, high: Int, match: Int): Int {
            if (match == evil.length) return 0
            if (pos == n) return 1
            if (dp[pos][low][high][match] != -1) return dp[pos][low][high][match]
            var ans = 0
            val from = if (low==1) s1[pos] else 'a'
            val to = if (high==1) s2[pos] else 'z'
            for (c in from..to) {
                var nxt = match
                while (nxt > 0 && c != evil[nxt]) nxt = fail[nxt-1]
                if (c == evil[nxt]) nxt++
                ans = (ans + dfs(pos+1, if (low==1&&c==from) 1 else 0, if (high==1&&c==to) 1 else 0, nxt)) % mod
            }
            dp[pos][low][high][match] = ans
            return ans
        }
        return dfs(0, 1, 1, 0)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

def findGoodStrings(n: int, s1: str, s2: str, evil: str) -> int:
    MOD = 10**9+7
    fail = [0]*len(evil)
    for i in range(1, len(evil)):
        j = fail[i-1]
        while j > 0 and evil[i] != evil[j]:
            j = fail[j-1]
        if evil[i] == evil[j]:
            fail[i] = j+1
    from functools import lru_cache
    @lru_cache(None)
    def dfs(pos: int, low: int, high: int, match: int) -> int:
        if match == len(evil): return 0
        if pos == n: return 1
        from_c = s1[pos] if low else 'a'
        to_c = s2[pos] if high else 'z'
        ans = 0
        for c in range(ord(from_c), ord(to_c)+1):
            nxt = match
            while nxt > 0 and chr(c) != evil[nxt]:
                nxt = fail[nxt-1]
            if chr(c) == evil[nxt]:
                nxt += 1
            ans = (ans + dfs(pos+1, low and chr(c)==from_c, high and chr(c)==to_c, nxt)) % MOD
        return ans
    return dfs(0, True, True, 0)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

impl Solution {
    pub fn find_good_strings(n: i32, s1: String, s2: String, evil: String) -> i32 {
        let modv = 1_000_000_007;
        let n = n as usize;
        let s1 = s1.as_bytes();
        let s2 = s2.as_bytes();
        let evil = evil.as_bytes();
        let mut fail = vec![0; evil.len()];
        for i in 1..evil.len() {
            let mut j = fail[i-1];
            while j > 0 && evil[i] != evil[j] {
                j = fail[j-1];
            }
            if evil[i] == evil[j] {
                fail[i] = j+1;
            }
        }
        let mut dp = vec![vec![vec![vec![-1; evil.len()]; 2]; 2]; n+1];
        fn dfs(pos: usize, low: usize, high: usize, matchv: usize, n: usize, s1: &[u8], s2: &[u8], evil: &[u8], fail: &[usize], dp: &mut Vec<Vec<Vec<Vec<i32>>>>) -> i32 {
            if matchv == evil.len() { return 0; }
            if pos == n { return 1; }
            if dp[pos][low][high][matchv] != -1 { return dp[pos][low][high][matchv]; }
            let mut ans = 0;
            let from = if low==1 { s1[pos] } else { b'a' };
            let to = if high==1 { s2[pos] } else { b'z' };
            for c in from..=to {
                let mut nxt = matchv;
                while nxt > 0 && c != evil[nxt] {
                    nxt = fail[nxt-1];
                }
                if c == evil[nxt] {
                    nxt += 1;
                }
                ans = (ans + dfs(pos+1, if low==1&&c==from {1} else {0}, if high==1&&c==to {1} else {0}, nxt, n, s1, s2, evil, fail, dp)) % 1_000_000_007;
            }
            dp[pos][low][high][matchv] = ans;
            ans
        }
        dfs(0, 1, 1, 0, n, &s1, &s2, &evil, &fail, &mut dp)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    findGoodStrings(n: number, s1: string, s2: string, evil: string): number {
        const MOD = 1e9+7;
        const fail = Array(evil.length).fill(0);
        for (let i = 1, j = 0; i < evil.length; i++) {
            while (j && evil[i] !== evil[j]) j = fail[j-1];
            if (evil[i] === evil[j]) fail[i] = ++j;
        }
        const dp = Array.from({length: n+1}, () => Array.from({length: 2}, () => Array.from({length: 2}, () => Array(evil.length).fill(-1))));
        function dfs(pos: number, low: number, high: number, match: number): number {
            if (match === evil.length) return 0;
            if (pos === n) return 1;
            if (dp[pos][low][high][match] !== -1) return dp[pos][low][high][match];
            let ans = 0;
            const from = low ? s1[pos] : 'a';
            const to = high ? s2[pos] : 'z';
            for (let c = from.charCodeAt(0); c <= to.charCodeAt(0); c++) {
                let nxt = match;
                while (nxt && String.fromCharCode(c) !== evil[nxt]) nxt = fail[nxt-1];
                if (String.fromCharCode(c) === evil[nxt]) nxt++;
                ans = (ans + dfs(pos+1, low && c === from.charCodeAt(0) ? 1 : 0, high && c === to.charCodeAt(0) ? 1 : 0, nxt)) % MOD;
            }
            dp[pos][low][high][match] = ans;
            return ans;
        }
        return dfs(0, 1, 1, 0);
    }
}

Complexity

  • ⏰ Time complexity: O(n * m * 26), where n is the string length and m is the evil length.
  • 🧺 Space complexity: O(n * m * 4), for the DP table.