[Java] 1ms Fastest DFS + Memorization beat 100% 100% - 46 lines only
Fastest verions is at the end of this post\nThe most difficult part of the DFS solution is to avoid counting more than once.\nLet\'s assume evil = \'abcab\'.\n 
**Fastest verions is at the end of this post**\nThe most difficult part of the DFS solution is to avoid counting more than once.\nLet\'s assume evil = \'abcab\'.\n* Convert n + 1 to n.\ncountGood([from], [to]) = Sum{ count([firstChar][n-1 chars]) where firstChar in ? between [from] and [to] } + (m - countEvil( abcab[n-5 chars] ) ) % m\n\n* Count the number of strings start with evil of length n;\nThe countEvil method count the string between [from] and [to] that **start with evil (not contains evil elsewhere!!!)**.\n  1) countEvil must count **the number of strings that start with evil**.\n  2) countEvil must remove **the number of string that start with evil and also contains evil in the middle**, because that number of deducted for smaller n. \n  \nFor example. when n = 9, evil = \'abcab\', from = \'aaaaaaaaa\', to = \'zzzzzzzzz\'. So we basically have \'?????????\' (9 chars). That\'s 26^9.\nThen let\'s count the number of strings start with \'abcab\', that would be \'abcab????\' (26^4), but \'abc**abcab**?\' (26^1) should be removed (from the number of strings start with \'abcab\') as it will be counted again for n = 6  \'??????\' (6 chars).\n\nTime Complexity: O(n * evil.length()) or O(n * (4 + offsets.size())) \nSpace Complexity: O(n * 3)\n\n**Version 1** The following verion is a bit easier to understand. It takes 20ms and around 42.5M memory.\n```Java\nclass Solution {\n    static long m = 1000000007L;\n    static String[] froms = new String[501], tos = new String[501]; // the default from and to boundaries;\n    String e; // evil\n    int el; // length of evil\n    ArrayList<Integer> offsets = new ArrayList(51);\n    HashMap<String, Long> goods = new HashMap();\n    public int findGoodStrings(int n, String s1, String s2, String evil) {\n        if(froms[0] == null){\n            froms[0] = "";\n            tos[0] = "";\n            for(int i = 1; i < 501; i++){ // build the default boundaries\n                froms[i] = froms[i - 1] + "a";\n                tos[i] = tos[i - 1] + "z";\n            }\n        }\n        goods.put("-", 1L); // the dp boundary condition. count 1 when from == to\n        e = evil;\n        el = e.length();\n        for(int i = 1; i < el; i++) if (evil.substring(i, el).equals(evil.substring(0, el - i))) offsets.add(i); // find internal overlaps in the evil such as [abc(ab]cab)\n        return (int)countGood(s1, s2);\n    }\n    long countGood(String from, String to){ // count the good strings between [from] and [to]\n        String key = from + "-" + to;\n        if(goods.containsKey(key)) return goods.get(key);\n        int l = from.length(), f = from.charAt(0) - \'a\', t = to.charAt(0) - \'a\';\n        long cnt = ((t > f + 1 ? countGood(froms[l - 1], tos[l - 1]) * (t - f - 1) : 0) + // count from \'a...a\' to \'z...z\' for chars between f and t\n                (t > f ? countGood(from.substring(1), tos[l - 1]) + countGood(froms[l - 1], to.substring(1)) : countGood(from.substring(1), to.substring(1))) + // count for char f and t\n                (m - countEvil(from, to, l))) % m; // remove the strings that start with evil\n        goods.put(key, cnt); // add to memorization\n        return cnt;\n    }\n    long countEvil(String from, String to, int l){ // count the strings between [from] and [to] that starts with evil\n        if(l < el) return 0L; // when string length is less than evil length, return 0\n        int compareFrom = e.compareTo(from.substring(0, el)), compareTo = e.compareTo(to.substring(0, el));\n        if(compareFrom < 0 || compareTo > 0) return 0L; // when evil can\'t appear in the range between from and to, return 0\n        long cnt = countGood(compareFrom == 0 ? from.substring(el) : froms[l - el], compareTo == 0 ? to.substring(el): tos[l - el]); // count good\n        for(int offset: offsets) // remove the duplicates, for cases such as abcab, where another abcab could start from inside [abc(ab]cab)\n            if(l - offset < el) break;\n            else cnt = (cnt + m - countEvil(from.substring(0, offset).equals(e.substring(0, offset)) ? from.substring(offset) : froms[l - offset],\n                    to.substring(0, offset).equals(e.substring(0, offset)) ? to.substring(offset) : tos[l - offset],l - offset)) % m;\n        return cnt;\n    }\n}\n```\n\n**Improvement by using arrays and avoiding substrings**\nIn the solution above, there are many HashMap and substring operations that are not necessary. In order to achieve the best performance, the strategy is to store the results in arrays, and to avoid substring operations in comparisons.\n\n**Fastest Version** By applying the above optimizations, the following improved version takes only 1ms and around 38M memory!\n```Java\nclass Solution {\n    static long m = 1000000007L;\n    String e, sourceFrom, sourceTo; // evil\n    int n, el; // length of evil\n    Long[] goodCounts, fullCounts, fromCounts, toCounts;\n    ArrayList<Integer> offsets = new ArrayList(51);\n    public int findGoodStrings(int n, String s1, String s2, String evil) {\n        e = evil;\n        sourceFrom = s1;\n        sourceTo = s2;\n        this.n = n;\n        goodCounts = new Long[n];\n        fullCounts = new Long[n];\n        fromCounts = new Long[n];\n        toCounts = new Long[n];\n        el = e.length();\n        for(int i = 1; i < el; i++) if(offsetCompare(i)) offsets.add(i);\n        return  (int)countGood(0);\n    }\n    boolean offsetCompare(int index){\n        int limit = el - index;\n        for(int i = 0; i < limit; i++)\n            if(e.charAt(i) != e.charAt(i + index))\n                return false;\n        return true;\n    }\n    long countGood(int index){\n        if(index == n) return 1;\n        if(goodCounts[index] != null) return goodCounts[index];\n        int f = sourceFrom.charAt(index) - \'a\', t = sourceTo.charAt(index) - \'a\';\n        long cnt = ((t - f > 1 ? countFull(index + 1) * (t - f - 1) : 0) +\n                (t > f ? countFrom(index + 1) + countTo(index + 1) : countGood(index + 1)) +\n                (m - countEvil(index))) % m;\n        goodCounts[index] = cnt;\n        return cnt;\n    }\n    long countFull(int index){\n        if(index == n) return 1;\n        if(fullCounts[index] != null) return fullCounts[index];\n        long cnt = (26 * countFull(index + 1) + (m - countEvilFull(index))) % m;\n        fullCounts[index] = cnt;\n        return cnt;\n    }\n    long countFrom(int index){\n        if(index == n) return 1;\n        if(fromCounts[index] != null) return fromCounts[index];\n        int f = sourceFrom.charAt(index) - \'a\';\n        long cnt = ((25 > f ? countFull(index + 1) * (25 - f) : 0) + countFrom(index + 1) + (m - countEvilFrom(index))) % m;\n        fromCounts[index] = cnt;\n        return cnt;\n    }\n    long countTo(int index){\n        if(index == n) return 1;\n        if(toCounts[index] != null) return toCounts[index];\n        int t = sourceTo.charAt(index) - \'a\';\n        long cnt = ((t > 0 ? countFull(index + 1) * (t - 0) : 0) + countTo(index + 1) + (m - countEvilTo(index))) % m;\n        toCounts[index] = cnt;\n        return cnt;\n    }\n    long countEvil(int index){\n        int endOfEvil = index + el;\n        if(endOfEvil > n) return 0L;\n        int compareFrom = compare(sourceFrom, index), compareTo = compare(sourceTo, index);\n        if(compareFrom < 0 || compareTo > 0) return 0L;\n        long cnt;\n        if(compareFrom == 0){\n            if(compareTo == 0)\n                cnt = countGood(endOfEvil);\n            else\n                cnt = countFrom(endOfEvil);\n        }\n        else{\n            if(compareTo == 0)\n                cnt = countTo(endOfEvil);\n            else\n                cnt = countFull(endOfEvil);\n        }\n        for(int offset: offsets)\n            if(endOfEvil + offset > n) break;\n            else {\n                if(compare(sourceFrom, index + offset) == 0){\n                    if(compare(sourceTo, endOfEvil + offset) == 0)\n                        cnt += m - countEvil(index + offset);\n                    else\n                        cnt += m - countEvilFrom(index + offset);\n                }\n                else{\n                    if(compare(sourceTo, index + offset) == 0)\n                        cnt += m - countEvilTo(index + offset);\n                    else\n                        cnt += m - countEvilFull(index + offset);\n                }\n            }\n        cnt %= m;\n        return cnt;\n    }\n    long countEvilFull(int index){\n        int endOfEvil = index + el;\n        if(endOfEvil > n) return 0L;\n        long cnt = countFull(endOfEvil);\n        for(int offset: offsets)\n            if(endOfEvil + offset > n) break;\n            else cnt += m - countEvilFull(index + offset);\n        return cnt % m;\n    }\n    long countEvilFrom(int index){\n        int endOfEvil = index + el;\n        if(endOfEvil > n) return 0L;\n        int compareFrom = compare(sourceFrom, index);\n        if(compareFrom < 0) return 0L;\n        long cnt = compareFrom == 0 ? countFrom(endOfEvil) : countFull(endOfEvil);\n        for(int offset: offsets)\n            if(endOfEvil + offset > n) break;\n            else cnt += m - (compare(sourceFrom, index + offset) == 0 ?  countEvilFrom(index + offset) : countEvilFull(index + offset));\n        return cnt % m;\n    }\n    long countEvilTo(int index){\n        int endOfEvil = index + el;\n        if(endOfEvil > n) return 0L;\n        int compareTo = compare(sourceTo, index);\n        if(compareTo > 0) return 0L;\n        long cnt = compareTo == 0 ? countTo(endOfEvil): countFull(endOfEvil);\n        for(int offset: offsets)\n            if(endOfEvil + offset > n) break;\n            else cnt += m - (compare(sourceTo, index + offset) == 0 ? countEvilTo(index + offset): countEvilFull(index + offset));\n        return cnt % m;\n    }\n\n    int compare(String value, int index){\n        int limit = Math.min(el, n - index);\n        for(int i = 0; i < limit; i++){\n            int delta = e.charAt(i) - value.charAt(i + index);\n            if(delta == 0) continue;\n            return delta;\n        }\n        return 0;\n    }\n}\n```
['Dynamic Programming', 'Depth-First Search', 'Memoization']