Really good hard probelm
This is a really good problem, The key idea here is observing that we have to track the idx in evil keeping in mind that adding a new character at any point cou
This is a really good problem, The key idea here is observing that we have to track the idx in evil keeping in mind that adding a new character at any point could potentially end up as a prefix for evil .\n```\nclass Solution {\n    int mod = (int) Math.pow(10, 9) + 7;\n\n    private int[][][][] newDp(int x, int y, int z, int t) {\n        int[][][][] dp = new int[x][y][z][t];\n        for (int[][][] a : dp) {\n            for (int[][] b : a) {\n                for (int[] c : b)\n                    Arrays.fill(c, -1);\n            }\n        }\n        return dp;\n    }\n\n    String s1, s2, evil;\n    int[][] eDp;\n\n    public int findGoodStrings(int n, String s1, String s2, String evil) {\n        long count = 0;\n        this.s1 = s1;\n        this.s2 = s2;\n        this.evil = evil;\n        eDp = solveE(evil);\n        int[][][][] dp = newDp(s1.length(), s2.length(), 2, 2);\n        for (char ch = s1.charAt(0); ch <= s2.charAt(0); ch++) {\n            count += solve(1, ch == evil.charAt(0) ? 1 : 0, s1.charAt(0) == ch ? 1 : 0, s2.charAt(0) == ch ? 1 : 0, dp);\n            count %= mod;\n        }\n        return (int) count % mod;\n    }\n\n    public int[][] solveE(String str) {\n        int[][] dp = new int[str.length() + 1][26];\n        StringBuffer b = new StringBuffer();\n        for (int i = 0; i < str.length(); i++) {\n            b.append(str.charAt(i));\n            for (char ch = \'a\'; ch <= \'z\'; ch++) {\n                b.append(ch);\n                for (int j = b.length() - 1; j >= 0; j--) {\n                    String s = b.substring(j, b.length());\n                    if (str.startsWith(s)) {\n                        dp[i + 1][ch - \'a\'] = s.length();\n                    }\n                }\n                b.deleteCharAt(b.length() - 1);\n            }\n        }\n        return dp;\n    }\n\n    private int solve(int idx, int eIdx, int isS1Prefix, int isS2Prefix, int[][][][] dp) {\n        if (eIdx >= evil.length()) {\n            return 0;\n        }\n        if (idx >= s1.length()) {\n            return 1;\n        }\n\n        if (dp[idx][eIdx][isS1Prefix][isS2Prefix] != -1) {\n            return dp[idx][eIdx][isS1Prefix][isS2Prefix];\n        }\n        long count = 0;\n        char start = \'a\', end = \'z\';\n        for (char ch = start; ch <= end; ch++) {\n            if ((isS2Prefix == 1 && ch > s2.charAt(idx)) || (isS1Prefix == 1 && ch < s1.charAt(idx))) {\n                continue;\n            }\n            if (ch == evil.charAt(eIdx)) {\n                count += solve(idx + 1, eIdx + 1, getPrefix(isS1Prefix, ch, s1.charAt(idx)),\n                        getPrefix(isS2Prefix, ch, s2.charAt(idx)), dp);\n            } else {\n                count += solve(idx + 1, eDp[eIdx][ch - \'a\'], getPrefix(isS1Prefix, ch, s1.charAt(idx)),\n                        getPrefix(isS2Prefix, ch\n                                , s2.charAt(idx)), dp);\n                count %= mod;\n            }\n        }\n        return dp[idx][eIdx][isS1Prefix][isS2Prefix] = (int) (count % mod);\n    }\n\n    private int getPrefix(int currPrefix, char ch, char toAdd) {\n        if (currPrefix == 1) {\n            return ch == toAdd ? 1 : 0;\n        }\n        return 0;\n    }\n}\n```
[]