The "Find All Good Strings" problem asks you to count the number of strings of a given length n that are lexicographically between two given strings s1 and s2 (inclusive), and do not contain a given evil substring. All strings are made up of lowercase English letters.
s1 and s2 are both of length n.x such that s1 ≤ x ≤ s2 and evil is not a substring of x.10^9 + 7.1 ≤ n ≤ 500, 1 ≤ evil.length ≤ 50, and all strings consist of lowercase letters.
At first glance, the problem seems to ask for generating all possible strings of length n between s1 and s2, filtering out those that contain evil, and counting the rest. However, with n up to 500, brute-forcing all possible strings is computationally infeasible because the number of strings grows exponentially (26^n).
Instead, we need to count the valid strings efficiently, without generating them. This leads us to dynamic programming (DP), where we can recursively count possibilities while keeping track of:
evil substring we've seen so far (to avoid forming it).s1) or upper bound (s2).
To efficiently check for the presence of evil, we use ideas from the Knuth-Morris-Pratt (KMP) algorithm, which allows us to track prefix matches in evil as we build the string.
The solution uses a digit DP (dynamic programming over digits/characters) with memoization, and a KMP-style automaton to avoid forming the evil substring.
evil to allow fast state transitions when matching prefixes.pos: Current position in the string we're building.matched: How many characters of evil we've matched so far.is_tight_low: Are we still matching the lower bound (s1)?is_tight_high: Are we still matching the upper bound (s2)?low to high depending on tightness), try extending the string.matched using the KMP automaton.matched equals evil.length, stop (invalid string).pos == n), count 1 valid string.s1 to s2 inclusive.10^9 + 7 as required.
Let's say n = 2, s1 = "aa", s2 = "da", and evil = "b".
s1[0]='a'), and can't go above 'd' (since s2[0]='d').O(26^n), which is infeasible for n up to 500.n positions, up to evil.length match states, and 2 tightness flags (for low/high) each.n * evil.length * 2 * 2 = up to 500 * 50 * 2 * 2 = 100,000 states.O(n * m * 2 * 2 * 26), where m = evil.length.O(n * m * 2 * 2) for memoization.The "Find All Good Strings" problem is a classic example of digit DP, where we efficiently count valid strings within bounds, avoiding forbidden substrings by leveraging KMP-style prefix matching. The key insight is to model the problem as a recursive state machine, tracking how much of the forbidden substring we've seen, and whether we're still tight to the lower or upper bounds. This approach avoids brute-force enumeration and makes the solution efficient and elegant, even for large inputs.
MOD = 10 ** 9 + 7
class Solution:
def findGoodStrings(self, n, s1, s2, evil):
m = len(evil)
# Build KMP failure function
fail = [0] * m
for i in range(1, m):
j = fail[i - 1]
while j > 0 and evil[i] != evil[j]:
j = fail[j - 1]
if evil[i] == evil[j]:
j += 1
fail[i] = j
from functools import lru_cache
@lru_cache(maxsize=None)
def dp(pos, matched, tight_low, tight_high):
if matched == m:
return 0
if pos == n:
return 1
res = 0
low = s1[pos] if tight_low else 'a'
high = s2[pos] if tight_high else 'z'
for c in range(ord(low), ord(high) + 1):
ch = chr(c)
k = matched
while k > 0 and evil[k] != ch:
k = fail[k - 1]
if evil[k] == ch:
k += 1
res += dp(
pos + 1,
k,
tight_low and ch == low,
tight_high and ch == high
)
res %= MOD
return res
return dp(0, 0, True, True)
#include <vector>
#include <string>
#include <cstring>
using namespace std;
const int MOD = 1e9 + 7;
class Solution {
public:
int n, m;
string s1, s2, evil;
vector<int> fail;
int memo[501][51][2][2];
void buildKMP() {
fail.assign(m, 0);
for (int i = 1; i < m; ++i) {
int j = fail[i - 1];
while (j > 0 && evil[i] != evil[j])
j = fail[j - 1];
if (evil[i] == evil[j]) ++j;
fail[i] = j;
}
}
int dp(int pos, int matched, bool tight_low, bool tight_high) {
if (matched == m) return 0;
if (pos == n) return 1;
int &res = memo[pos][matched][tight_low][tight_high];
if (res != -1) return res;
res = 0;
char low = tight_low ? s1[pos] : 'a';
char high = tight_high ? s2[pos] : 'z';
for (char ch = low; ch <= high; ++ch) {
int k = matched;
while (k > 0 && evil[k] != ch)
k = fail[k - 1];
if (evil[k] == ch) ++k;
res = (res + dp(pos + 1, k, tight_low && ch == low, tight_high && ch == high)) % MOD;
}
return res;
}
int findGoodStrings(int n_, string s1_, string s2_, string evil_) {
n = n_; s1 = s1_; s2 = s2_; evil = evil_;
m = evil.length();
buildKMP();
memset(memo, -1, sizeof(memo));
return dp(0, 0, 1, 1);
}
};
class Solution {
static final int MOD = 1000000007;
int n, m;
String s1, s2, evil;
int[] fail;
Integer[][][][] memo;
void buildKMP() {
fail = new int[m];
for (int i = 1; i < m; ++i) {
int j = fail[i - 1];
while (j > 0 && evil.charAt(i) != evil.charAt(j))
j = fail[j - 1];
if (evil.charAt(i) == evil.charAt(j)) ++j;
fail[i] = j;
}
}
int dp(int pos, int matched, boolean tightLow, boolean tightHigh) {
if (matched == m) return 0;
if (pos == n) return 1;
if (memo[pos][matched][tightLow ? 1 : 0][tightHigh ? 1 : 0] != null)
return memo[pos][matched][tightLow ? 1 : 0][tightHigh ? 1 : 0];
int res = 0;
char low = tightLow ? s1.charAt(pos) : 'a';
char high = tightHigh ? s2.charAt(pos) : 'z';
for (char ch = low; ch <= high; ++ch) {
int k = matched;
while (k > 0 && evil.charAt(k) != ch)
k = fail[k - 1];
if (evil.charAt(k) == ch) ++k;
res = (res + dp(pos + 1, k, tightLow && ch == low, tightHigh && ch == high)) % MOD;
}
return memo[pos][matched][tightLow ? 1 : 0][tightHigh ? 1 : 0] = res;
}
public int findGoodStrings(int n_, String s1_, String s2_, String evil_) {
n = n_; s1 = s1_; s2 = s2_; evil = evil_;
m = evil.length();
buildKMP();
memo = new Integer[n + 1][m + 1][2][2];
return dp(0, 0, true, true);
}
}
const MOD = 1e9 + 7;
var findGoodStrings = function(n, s1, s2, evil) {
const m = evil.length;
// Build KMP failure function
const fail = new Array(m).fill(0);
for (let i = 1; i < m; ++i) {
let j = fail[i - 1];
while (j > 0 && evil[i] !== evil[j]) {
j = fail[j - 1];
}
if (evil[i] === evil[j]) ++j;
fail[i] = j;
}
const memo = new Map();
function dp(pos, matched, tightLow, tightHigh) {
if (matched === m) return 0;
if (pos === n) return 1;
const key = [pos, matched, tightLow, tightHigh].join(',');
if (memo.has(key)) return memo.get(key);
let res = 0;
let low = tightLow ? s1[pos] : 'a';
let high = tightHigh ? s2[pos] : 'z';
for (let c = low.charCodeAt(0); c <= high.charCodeAt(0); ++c) {
let ch = String.fromCharCode(c);
let k = matched;
while (k > 0 && evil[k] !== ch) {
k = fail[k - 1];
}
if (evil[k] === ch) ++k;
res = (res + dp(pos + 1, k, tightLow && ch === low, tightHigh && ch === high)) % MOD;
}
memo.set(key, res);
return res;
}
return dp(0, 0, true, true);
};