Formatted question description: https://leetcode.ca/all/1397.html

# 1397. Find All Good Strings (Hard)

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:51Explanation: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:0Explanation: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`

`1 <= n <= 500`

`1 <= evil.length <= 50`

- All strings consist of lowercase English letters.

**Related Topics**:

Dynamic Programming

## Solution 1.

Let `dp[i][j][k]`

Let `tr[i][j]`

be the maximum suffix length if we prepend character `'a' + j`

to a `e`

’s suffix of size `i`

.

For example, if `e = "abab"`

, `i = 2`

, `j = 1`

, so the new suffix we get by prepending `'a' + 1 = 'b'`

to `e[0..(i-1)] = "ab"`

is `"bab"`

, and `"bab"`

is a suffix of `e`

that is of size `3`

. So `tr[2][1] = 3`

.

https://www.youtube.com/watch?v=uqdsHJzlsIc Digit DP: https://codeforces.com/blog/entry/53960

```
```

Java

```
class Solution {
public int findGoodStrings(int n, String s1, String s2, String evil) {
int length = evil.length();
int[][][] dp = new int[n][length][4];
for (int i = 0; i < n; i++) {
for (int j = 0; j < length; j++) {
for (int k = 0; k < 4; k++)
dp[i][j][k] = -1;
}
}
int[][] transfers = new int[length][26];
for (int i = 0; i < length; i++) {
for (int j = 0; j < 26; j++)
transfers[i][j] = -1;
}
int[] fails = new int[length];
for (int i = 1; i < length; i++) {
int state = fails[i - 1];
while (state > 0 && evil.charAt(state) != evil.charAt(i))
state = fails[state - 1];
if (evil.charAt(state) == evil.charAt(i))
fails[i] = state + 1;
}
return depthFirstSearch(n, s1, s2, evil, dp, transfers, fails, 0, 0, 3);
}
public int depthFirstSearch(int n, String s1, String s2, String evil, int[][][] dp, int[][] transfers, int[] fails, int index, int state, int bound) {
final int MODULO = 1000000007;
int length = evil.length();
if (state == length)
return 0;
if (index == n)
return 1;
if (dp[index][state][bound] >= 0)
return dp[index][state][bound];
dp[index][state][bound] = 0;
char low = ((bound & 1) > 0) ? s1.charAt(index) : 'a';
char high = ((bound & 2) > 0) ? s2.charAt(index) : 'z';
for (char c = low; c <= high; c++) {
int nextState = getTransfer(evil, transfers, fails, state, c);
int nextBound = 0;
if ((bound & 1) > 0 && c == s1.charAt(index))
nextBound++;
if ((bound & 2) > 0 && c == s2.charAt(index))
nextBound += 2;
dp[index][state][bound] = (dp[index][state][bound] + depthFirstSearch(n, s1, s2, evil, dp, transfers, fails, index + 1, nextState, nextBound)) % MODULO;
}
return dp[index][state][bound];
}
public int getTransfer(String evil, int[][] transfers, int[] fails, int state, char letter) {
int letterIndex = letter - 'a';
if (transfers[state][letterIndex] >= 0)
return transfers[state][letterIndex];
while (state > 0 && evil.charAt(state) != letter)
state = fails[state - 1];
int transfer = evil.charAt(state) == letter ? state + 1 : 0;
transfers[state][letterIndex] = transfer;
return transfer;
}
}
```