# Find All Good Strings **Difficulty:** HARD [External](https://leetcode.com/problems/find-all-good-strings) Canonical: https://scaleengineer.com/dsa/problems/find-all-good-strings **Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [String Matching](https://scaleengineer.com/dsa/patterns/string-matching) **Data structures:** String **Companies:** [Dunzo](https://scaleengineer.com/companies/dunzo) --- ## 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** `109 + 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` * `s1 <= s2` * `1 <= n <= 500` * `1 <= evil.length <= 50` * All strings consist of lowercase English letters. # Approaches ## Digit DP with KMP (On-the-fly Transitions) This approach uses dynamic programming on strings, often called "Digit DP", combined with the Knuth-Morris-Pratt (KMP) algorithm. We build the desired strings character by character, keeping track of constraints. The state of our DP includes the current index, whether we are tightly bound by the upper-limit string, and the length of the matched prefix of the `evil` string. In this version, the KMP state transitions are computed on-the-fly during the recursion. **Time:** O(n * m * 26 * m), where `n` is string length and `m` is `evil`'s length. The DP has `n * m * 2` states. Each state computation involves a loop of up to 26 characters, and inside it, `getNextEvilMatch` takes O(m) time. The initial LPS array construction takes O(m). · **Space:** O(n * m), where `n` is the length of the strings and `m` is the length of `evil`. This is for the memoization table `memo[n][m][2]`. The LPS array takes an additional O(m) space. **Pros:** Correctly solves the problem by handling all constraints.; The logic is relatively intuitive for those familiar with Digit DP.; Requires less precomputation than the optimized approach. **Cons:** Slower than the precomputation approach because the KMP state transition is recalculated repeatedly inside the DP loops.; For very tight time limits, this approach might be too slow compared to the optimized version. ### Explanation The problem asks for the number of "good" strings in a range `[s1, s2]`. This can be calculated as `count(s2) - count(s1) + (is s1 good?)`, where `count(S)` is the number of good strings lexicographically less than or equal to `S`. We define a recursive function `solve(index, evilMatch, isTight)` which counts the number of ways to complete a valid string from `index` given the current state. - `index`: The current character position we are filling (from 0 to `n-1`). - `evilMatch`: The length of the current suffix of our string that is also a prefix of `evil`. - `isTight`: A boolean flag. If true, we can only place characters up to `S.charAt(index)`. Otherwise, we can place any character up to 'z'. The transitions involve iterating through all possible characters for the current `index`. For each character, we determine the next `evilMatch` state. This is done by simulating the KMP state transition, which requires pre-calculating the KMP's Longest Proper Prefix which is also Suffix (LPS) array for `evil`. Memoization is used to store the results of `dp[index][evilMatch][isTight]` to avoid recomputing states. ```java class Solution { int[][][] memo; String s1, s2, evil; int n, m; int[] lps; int MOD = 1_000_000_007; public int findGoodStrings(int n, String s1, String s2, String evil) { this.s1 = s1; this.s2 = s2; this.evil = evil; this.n = n; this.m = evil.length(); buildLPS(); int countS2 = count(s2); int countS1 = count(s1); int ans = (countS2 - countS1 + MOD) % MOD; if (!s1.contains(evil)) { ans = (ans + 1) % MOD; } return ans; } private int count(String S) { memo = new int[n][m][2]; for (int[][] a2 : memo) { for (int[] a1 : a2) { java.util.Arrays.fill(a1, -1); } } return dp(0, 0, true, S); } private int dp(int index, int evilMatch, boolean isTight, String S) { if (evilMatch == m) { return 0; // Found evil string } if (index == n) { return 1; // Found a valid good string } if (memo[index][evilMatch][isTight ? 1 : 0] != -1) { return memo[index][evilMatch][isTight ? 1 : 0]; } long res = 0; char upperBound = isTight ? S.charAt(index) : 'z'; for (char c = 'a'; c <= upperBound; c++) { int nextEvilMatch = getNextEvilMatch(evilMatch, c); boolean nextIsTight = isTight && (c == upperBound); res = (res + dp(index + 1, nextEvilMatch, nextIsTight, S)) % MOD; } return memo[index][evilMatch][isTight ? 1 : 0] = (int) res; } private int getNextEvilMatch(int currentMatch, char c) { while (currentMatch > 0 && evil.charAt(currentMatch) != c) { currentMatch = lps[currentMatch - 1]; } if (evil.charAt(currentMatch) == c) { currentMatch++; } return currentMatch; } private void buildLPS() { lps = new int[m]; if (m == 0) return; int length = 0; int i = 1; while (i < m) { if (evil.charAt(i) == evil.charAt(length)) { length++; lps[i] = length; i++; } else { if (length != 0) { length = lps[length - 1]; } else { lps[i] = 0; i++; } } } } } ``` ### Algorithm - The core idea is to count the number of good strings in the range `[s1, s2]` using the principle of inclusion-exclusion: `count(s2) - count(s1) + (is s1 good?)`. The function `count(S)` calculates the number of good strings lexicographically less than or equal to `S`. - We implement `count(S)` using a top-down dynamic programming approach with memoization. The state is defined by `dp(index, evilMatch, isTight)`. - `index`: The current character position (0 to `n-1`) we are building. - `evilMatch`: The length of the current suffix of the constructed string that is also a prefix of `evil`. This tracks our proximity to forming the `evil` string. - `isTight`: A boolean flag indicating if our choices are restricted by the characters of `S`. If true, the character at `index` can be at most `S.charAt(index)`; otherwise, it can be any character from 'a' to 'z'. - The KMP algorithm's Longest Proper Prefix Suffix (LPS) array is pre-calculated for `evil`. This array is used to determine the next `evilMatch` state. - The recursive function explores all valid character choices at each position. For each choice, it calculates the `nextEvilMatch` state on-the-fly using the current state, the chosen character, and the LPS array. - The base cases for the recursion are: - If `evilMatch` equals `evil.length()`, the path is invalid, return 0. - If `index` reaches `n`, a valid string has been formed, return 1. - Results for each state are memoized to avoid redundant computations. ## Digit DP with KMP (Precomputed Transitions) This is an optimized version of the previous Digit DP approach. The core logic remains the same, but we introduce a significant performance improvement by precomputing the entire state transition table for the KMP automaton. This allows for O(1) state transitions within the DP, making it much faster. **Time:** O((n * m + m) * 26), which simplifies to O((n+1) * m * 26). The precomputation of the KMP transition table takes O(m * 26). The DP calculation has `n * m * 2` states, and each state takes O(26) time to compute. This is the most efficient time complexity achievable. · **Space:** O(n * m + m * 26). The memoization table requires O(n * m) space, and the precomputed KMP transition table requires O(m * 26) space. **Pros:** Highly efficient and the optimal solution for the given constraints.; The O(1) state transition lookup significantly speeds up the DP calculation. **Cons:** Requires additional space for the KMP transition table, `O(m * 26)`.; The precomputation step adds a bit of code complexity, although it's a standard KMP automaton construction. ### Explanation This approach refines the previous one by optimizing the KMP state transition calculation. The problem is still broken down into `count(s2) - count(s1) + (is s1 good?)`, and the DP state `solve(index, evilMatch, isTight)` is the same. The main enhancement is to pre-calculate a KMP transition table, `kmpNextState[m][26]`, before the DP process begins. This table maps a `(current_evil_match, next_character)` pair to the `next_evil_match` state. Building this table takes `O(m * 26)` time, where `m` is the length of `evil`. With this table, the step inside the DP's character loop that determines the next state becomes an efficient `O(1)` array lookup. This eliminates the `O(m)` work that was previously done for each character in each state, leading to a much better overall time complexity. ```java class Solution { int[][][] memo; int[][] kmpNextState; String s1, s2, evil; int n, m; int MOD = 1_000_000_007; public int findGoodStrings(int n, String s1, String s2, String evil) { this.s1 = s1; this.s2 = s2; this.evil = evil; this.n = n; this.m = evil.length(); buildKMPNextState(); int countS2 = count(s2); int countS1 = count(s1); int ans = (countS2 - countS1 + MOD) % MOD; if (m == 0 || !s1.contains(evil)) { ans = (ans + 1) % MOD; } return ans; } private int count(String S) { memo = new int[n][m][2]; for (int[][] a2 : memo) { for (int[] a1 : a2) { java.util.Arrays.fill(a1, -1); } } return dp(0, 0, true, S); } private int dp(int index, int evilMatch, boolean isTight, String S) { if (evilMatch == m) { return 0; // Found evil string } if (index == n) { return 1; // Found a valid good string } if (memo[index][evilMatch][isTight ? 1 : 0] != -1) { return memo[index][evilMatch][isTight ? 1 : 0]; } long res = 0; char upperBound = isTight ? S.charAt(index) : 'z'; for (char c = 'a'; c <= upperBound; c++) { int nextEvilMatch = kmpNextState[evilMatch][c - 'a']; boolean nextIsTight = isTight && (c == upperBound); res = (res + dp(index + 1, nextEvilMatch, nextIsTight, S)) % MOD; } return memo[index][evilMatch][isTight ? 1 : 0] = (int) res; } private void buildKMPNextState() { kmpNextState = new int[m][26]; if (m == 0) return; int[] lps = new int[m]; int length = 0; int i = 1; while (i < m) { if (evil.charAt(i) == evil.charAt(length)) { lps[i++] = ++length; } else { if (length != 0) length = lps[length - 1]; else i++; } } for (int j = 0; j < m; j++) { for (int c_idx = 0; c_idx < 26; c_idx++) { char c = (char) ('a' + c_idx); int currentMatch = j; while (currentMatch > 0 && evil.charAt(currentMatch) != c) { currentMatch = lps[currentMatch - 1]; } if (evil.charAt(currentMatch) == c) { currentMatch++; } kmpNextState[j][c_idx] = currentMatch; } } } } ``` ### Algorithm - The overall structure is identical to the previous approach: use `count(s2) - count(s1) + (is s1 good?)` and a recursive DP function `solve(index, evilMatch, isTight)`. - The key optimization is to precompute all possible KMP state transitions before starting the DP. - We create a 2D array, `kmpNextState[currentState][char]`, which stores the next KMP state for every possible current state (`0` to `m-1`) and every character ('a' to 'z'). - This transition table is built once using the LPS array of `evil`. The time to build this table is `O(m * 26)`. - During the DP recursion, instead of calculating the `nextEvilMatch` state in a loop, we perform a simple `O(1)` lookup in the `kmpNextState` table. - This reduces the complexity of each DP state calculation from `O(26 * m)` to `O(26)`, significantly improving the total runtime. # Solutions ### Java ```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 ; } } ```