Java | No KMP | DP
because the evil length is at most 50, we don\'t really need KMP. \n\nThe difficult part about this problem, in my opinion, is that when we are adding a charact
because the evil length is at most 50, we don\'t really need KMP. \n\nThe difficult part about this problem, in my opinion, is that when we are adding a character (from the end to the front), and if it does not match with the current streak of evil string, then we must know where it ends. It is not just 0 or 1. For example, say, we are at "cabc" and evil = "xcabc". The current streak is 4, then if we add \'b\' at the front, the streak does not get reset, it becomes 2 because "bc..." matches "...bc" in the evil string.\n\nWe can preprocess the above in naive `O(26 * E^3)`, which is ok since `E` is capped at 50.\n\nThe rest is digit DP.\n\n#### Java\n\n```Java\nclass Solution {\n    int M = (int)1e9+7;\n    public int findGoodStrings(int n, String s1, String s2, String evil) {\n        int[][] where = new int[evil.length()][26];\n        for (int i = 0; i < evil.length(); i++){ // preprocess suffix / prefix matching streak\n            String s = evil.substring(evil.length()-i);\n            for (int j = 0; j < 26; j++){ \n                String ns = ""+(char)(j+\'a\')+s;\n                for (int k = ns.length(); k >= 0; k--){\n                    if (evil.endsWith(ns.substring(0, k))){\n                        where[i][j]=k;\n                        break;\n                    }\n                }\n            }\n        }\n        int ans = solve(s2, evil, where) - solve(s1, evil, where) + M;\n        return ans%M + (s2.contains(evil)? 0 : 1);\n    }\n\t// dp[i][j][k] -> num of ways from the last i characters with j streaks, k = 0 if less than s, 1 otherwise.\n    private int solve(String s, String evil, int[][] where){\n        int[][][] dp = new int[s.length()+1][evil.length()+1][2]; \n        dp[s.length()][0][1]=1; // empty string is BIGGER (or I should say, "not less")\n        for (int i = s.length()-1; i >= 0; i--){\n            for (int j = 0; j < evil.length(); j++){\n                for (int k = 0; k < 26; k++){\n                    for (int c = 0; c < 2; c++){\n                        int nc = c;\n                        if (k < s.charAt(i) - \'a\'){\n                            nc=0;\n                        }else if (k > s.charAt(i) - \'a\'){\n                            nc=1;\n                        }\n                        dp[i][where[j][k]][nc]+=dp[i+1][j][c];\n                        dp[i][where[j][k]][nc]%=M;\n                    }\n                }\n            }\n        }\n        int ans = 0;\n        for (int i = 0; i < evil.length(); i++){\n            ans += dp[0][i][0]; // want strictly less \n            ans %= M;\n        }\n        return ans;\n    }\n}\n```
['Dynamic Programming', 'Java']