Detailed Intuitive Solution using Top Down DP and KMP
---\n\n## Problem Summary\n\nGiven two strings s1 and s2 of length n, and a "forbidden" substring evil, the goal is to find the number of strings of length n th
---\n\n## Problem Summary\n\nGiven two strings `s1` and `s2` of length `n`, and a "forbidden" substring `evil`, the goal is to find the number of strings of length `n` that:\n1. Are lexicographically between `s1` and `s2`.\n2. Do not contain the substring `evil`.\n\nSince the answer can be large, we need to return the result modulo \\(10^9 + 7\\).\n\n## Approach\n\nThe solution uses **Dynamic Programming (DP)** combined with the **Knuth-Morris-Pratt (KMP) prefix function** for efficient substring matching.\n\n### Key Concepts\n\n1. **Dynamic Programming**: The solution uses a 4-dimensional DP array `dp[index][evilMatched][leftBound][rightBound]` to store intermediate results:\n   - `index`: The current position in the string being formed.\n   - `evilMatched`: The length of the prefix of `evil` matched so far.\n   - `leftBound`: Indicates if the current string is still bounded by `s1`.\n   - `rightBound`: Indicates if the current string is still bounded by `s2`.\n\n2. **Prefix Function (KMP)**: This function tracks the longest prefix of `evil` that can continue to match, allowing the algorithm to avoid redundant calculations. If a match is interrupted, it "falls back" to a shorter potential prefix match using the `lps` array.\n\n3. **Recursive DFS with Memoization**: The function `dfs` is used to explore each character position in the candidate string, following the lexicographic bounds and matching progress on `evil`. Memoization is achieved by storing results in `dp` to avoid recalculating subproblems.\n\n### DP Transition Logic\n\nFor each character position in the candidate string:\n1. **Set Character Bounds**:\n   - If we are still under the `s1` bound, the character choice should be no less than `s1[index]`.\n   - Similarly, if under the `s2` bound, the character choice should be no more than `s2[index]`.\n\n2. **Update Evil Match Progress**:\n   - For each character `c`, update `evilMatched` based on whether `c` extends the match of `evil`.\n   - If `c` matches, increment the match length using the KMP prefix function to handle partial matches efficiently.\n\n3. **Recursive State Transition**:\n   - Call `dfs` for the next position with updated bounds and match progress, storing the result to avoid recomputation.\n\n### Complexity Analysis\n\n- **Time Complexity**: \\(O(n \\times m \\times 2 \\times 2 \\times 26)\\), where `n` is the length of `s1`/`s2`, `m` is the length of `evil`, `2` is for bound states, and `26` is for the alphabet size.\n- **Space Complexity**: \\(O(n \\times m \\times 2 \\times 2)\\) for the DP table.\n\n## Code Explanation\n\n```cpp\nclass Solution {\npublic:\n    int mod = 1e9+7;\n    int dp[501][51][2][2] = {};\n\n    int dfs(int index, int evilMatched, bool leftBound, bool rightBound, int n, string &s1, string &s2, string &evil, const vector<int> &lps) {\n        // Base cases\n        if (evilMatched == evil.size()) return 0; // Found `evil`, so it\'s invalid\n        if (index == n) return 1; // Valid string of length `n`\n        \n        // Check memoized result\n        if (dp[index][evilMatched][leftBound][rightBound] != 0) {\n            return dp[index][evilMatched][leftBound][rightBound];\n        }\n        \n        char from = leftBound ? s1[index] : \'a\';\n        char to = rightBound ? s2[index] : \'z\';\n\n        int result = 0;\n        for (char c = from; c <= to; c++) {\n            int j = evilMatched;\n            \n            // Update `evil` match length using KMP fallback\n            while (j > 0 && evil[j] != c) j = lps[j - 1];\n            if (c == evil[j]) j++;\n            \n            // Recursive DFS for next position\n            result += dfs(index + 1, j, leftBound && (c == from), rightBound && (c == to), n, s1, s2, evil, lps);\n            result %= mod; // Ensure modulo\n        }\n        \n        // Memoize result\n        return dp[index][evilMatched][leftBound][rightBound] = result;\n    }\n\n    vector<int> lps(string s) {\n        int n = s.length();\n        int len = 0;\n        int i = 1;\n        vector<int> result(n, 0);\n        \n        while (i < n) {\n            if (s[i] == s[len]) {\n                result[i++] = ++len;\n            } else if (len > 0) {\n                len = result[len - 1];\n            } else {\n                result[i++] = 0;\n            }\n        }\n        return result;\n    }\n\n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        const vector<int> lp = lps(evil); // Precompute LPS array for `evil`\n        return dfs(0, 0, true, true, n, s1, s2, evil, lp);\n    }\n};\n```\n\n### Explanation of Key Functions\n\n1. **`dfs`**:\n   - This recursive function builds strings character-by-character, tracking the evil match progress (`evilMatched`) and whether we\'re still within bounds (`leftBound`, `rightBound`).\n   - It uses the `lps` array to manage matches with `evil` efficiently.\n   - Memoization in `dp` saves repeated computations for each state.\n\n2. **`lps`**:\n   - This helper function calculates the **Longest Prefix Suffix (LPS)** array for `evil` using the KMP algorithm, allowing efficient substring matching by keeping track of how much of `evil` has been matched at each position.\n\n## Example Walkthrough\n\nLet\'s say `n = 3`, `s1 = "acb"`, `s2 = "bdc"`, and `evil = "ab"`.\n1. Start with the first character, bounded by `s1` and `s2`.\n2. For each character choice, check if it forms `evil`.\n3. Use `lps` to handle partial matches of `evil` without restarting.\n4. Continue recursively, updating bounds and `evilMatched`, until we reach length `n` or match `evil`.\n\nThis process results in the count of valid strings, modulo \\(10^9 + 7\\).\n\n## Conclusion\n\nThis optimized approach leverages DP with KMP substring matching, making it efficient for large inputs. The combination of bounds checking, prefix function, and memoization makes this solution both powerful and concise.\n\n---
['String', 'Dynamic Programming', 'String Matching', 'C++']