Welcome to Subscribe On Youtube
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: 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:
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
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..(i1)] = "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

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; } }
