Accepted Java solution, DP+KMP with explanation
At first I got a wrong solution https://leetcode.com/problems/find-all-good-strings/discuss/554856/What\'s-wrong-with-this-dp-solution\n\nbut now I finally pass
At first I got a wrong solution https://leetcode.com/problems/find-all-good-strings/discuss/554856/What\'s-wrong-with-this-dp-solution\n\nbut now I finally passed it thanks to @infinity4471 \n\ndp states: we are at current position i, matched evil string up to j (j at evial is waiting for a match), whether we are == s1, whether we are ==s2\n\ntransition: \n\n1) if eq1==0 and eq2==0, means we are >s1 and <s2, we can choose anything, even if the char is <s1.at(i) or >s2.at(i)\n2) if one of eq is 1, then it means we have to choose those >=s1 or <=s2 chars. Note when they are both 1 we have to choose >=s1 AND <=s2\n3) The evil string part is tricky. At first I always made the new j nj = 0 or 1, but as @infinity4471 pointed out in the above post we may get a partial match. Quoting him here\n\n"For example: suppose evil = "ababac" and you have in your current dp "ababa", suppose that you choose to add the character b at the end, therefore in your solution j will become 0 in the next recursive call. The thing is your string is now "ababab" and therefore the last 4 characters "abab" are a valid prefix of the evil string. Thus j must be 4, the way to go is to compute the KMP prefix function and use it when trying to change your j in your recursive calls."\n\n```\nclass Solution {\n    // dp + kmp\n    // have to use kmp because if we get a mismatch with evil we need kmp to "slide" to the next evil position to match with\n    private int Mod = 1000000007;\n    int[][][][] dp;\n    int[] nexts;\n\n    public int findGoodStrings(int n, String s1, String s2, String evil) {\n        dp = new int[s1.length() + 1][evil.length() + 1][2][2];\n        nexts = nexts(evil);\n        for (int i = 0; i < dp.length; i++) {\n            for (int j = 0; j < dp[i].length; j++) {\n                for (int k = 0; k < dp[i][j].length; k++) {\n                    Arrays.fill(dp[i][j][k], -1);\n                }\n            }\n        }\n        return dof(0, 0, 1, 1, n, s1, s2, evil);\n    }\n\n    private int dof(int i, int j, int eq1, int eq2, int n, String s1, String s2, String evil) {\n        if (j == evil.length()) {\n            return 0;\n        }\n        if (i == n) {\n            return 1;\n        }\n        if (dp[i][j][eq1][eq2] != -1L) {\n            return dp[i][j][eq1][eq2];\n        }\n        long r = 0L;\n        for (int k = 0; k < 26; k++) {\n            char c = (char) (k + \'a\');\n            int nj = j;\n            // if 0..j in evial doesnt match what we have, there could be 0...p where p<j and match with current string\n            // we use kmp to "slide" into that p position\n            while (nj > 0 && evil.charAt(nj) != c) {\n                nj = nexts[nj - 1];\n            }\n            nj = evil.charAt(nj) == c ? nj + 1 : nj;\n            if (eq1 == 0 && eq2 == 0) {\n                // >1 but <2, any can go\n                r += dof(i + 1, nj, 0, 0, n, s1, s2, evil);\n                r %= Mod;\n            } else if (eq1 == 1 && eq2 == 1) {\n                // ==1 and ==2. we may be able to change eq1 and eq2 but must folow the rule for 1 and 2\n                if (c >= s1.charAt(i) && c <= s2.charAt(i)) {\n                    int neq1 = c > s1.charAt(i) ? 0 : 1;\n                    int neq2 = c < s2.charAt(i) ? 0 : 1;\n                    r += dof(i + 1, nj, neq1, neq2, n, s1, s2, evil);\n                    r %= Mod;\n                }\n            } else if (eq1 == 1 && eq2 == 0) {\n                // ==1, but <2\n                if (c >= s1.charAt(i)) {\n                    int neq1 = c > s1.charAt(i) ? 0 : 1;\n                    r += dof(i + 1, nj, neq1, 0, n, s1, s2, evil);\n                    r %= Mod;\n                }\n            } else {\n                // >1 but ==2\n                if (c <= s2.charAt(i)) {\n                    int neq2 = c < s2.charAt(i) ? 0 : 1;\n                    r += dof(i + 1, nj, 0, neq2, n, s1, s2, evil);\n                    r %= Mod;\n                }\n            }\n        }\n        dp[i][j][eq1][eq2] = (int) (r % Mod);\n        return dp[i][j][eq1][eq2];\n    }\n\n    // kmp next array\n    private int[] nexts(String s) {\n        int n = s.length();\n        int[] next = new int[n];\n        next[0] = 0;// length of the longest prefix: 0...next[i] -1 == the prefix. the suffix ends at i\n        for (int i = 1; i < n; i++) {\n            char c = s.charAt(i);\n            // abaaabab, macthing at the last b\n            // when we mismatch with pos j, we try out next[j-1] it\'s a shorter prefix but may give new hope\n            int j = next[i - 1];\n            while (j > 0 && c != s.charAt(j)) {\n                j = next[j - 1];\n            }\n            // if j==0 give a chance to match s[0]\n            if (c == s.charAt(j)) {\n                next[i] = j + 1;\n            }\n        }\n        return next;\n    }\n}\n```\n```
[]