Python 3: Top-Down DFS with Caching and KMP
Intuition\n\nThis is similar to the other solutions; I only got to this\nby glancing at a few other solutions, then doing it myself.\n\nAfter looking at some ot
# Intuition\n\nThis is similar to the other solutions; I only got to this\nby glancing at a few other solutions, then doing it myself.\n\nAfter looking at some others in more detail I think this is better written so I thought I\'d share.\n\nThe idea is that we want to return the number of `n` character strings in `[s1, s2]` that have no matches to `evil` anywhere.\n\nI call this "count with restrictions." With usually involves top-down DFS or DP.\n\n## Count With Restrictions\n\nWhen we need to generate things subject to restrictions, like "the past `k` characters don\'t match `evil`", the annswer is usually easiest with top-down DFS.\n\nHere we\'re generating strings so we go character by character. This can probably be sped up; the fastest solutions (which are mostly copies of each other!) seem to do some clever things about *calculating the number of options* rather than brute-force enumerating over all the options as done here.\n\nAnyway, we think about what happens when we add the character `c` at index `i` to our strings as we build strings in [s1, s2]:\n* if c would make the string lower than s1, skip it\n* if c matches the next character in `evil`, continue but record that we matched another character. If it doesn\'t, then find the new longest suffix in `evil` that matches (hence all the KMP stuff). Not matching a character means the suffix is shorter, but it does NOT mean it\'s zero!\n* if c would make the string higher than s2, skip it\n\n# Approach\n\nIn this solution I do a pretty brute-force top-down DFS.\n\nI enumerate over all possible characters we can use at each index\n\nThis could probably be a lot faster if we could calculate the number of such characters, as I think the faster solutions do. But you have to be careful about maintaining the right value of `k`\n\n# Techniques\n\n## Generating Sequences in Lexicographical Bounds\n\nThe `m1: bool, m2: bool` arguments (or DP table indices) are VERY common in generating strings in bounds.\n\nThe idea is that\n* if we\'ve matched all characters thus far, the prefixes are equal\n* therefore the next character will determine if\n  * the string is less than the target: `c < s[i]`\n  * the string is still equal to the target so far: `c == s[i]`\n  * the string is greater than the target: `c > s[i]`\n\nRather than store the actual strings (too expensive when doing combinations problems), we instead just keep a `bool` that records whether they\'ve matched.\n\n## Generating Sequences with Constraints\n\nWhen we have constraints, the DP or DFS needs to have extra variables that represent the "state" of the constraint.\n\nCommon constraint examples:\n* no more than three copies of any character in a row\n  * state: prior character and the number of copies of it (usually)\n* no more than three copies of any character in total\n  * state: count of each character thus far (usually)\n\nLess common constraint examples:\n* can\'t match `evil`\n  * state: how many chars we\'ve matched in `evil` thus far (aka "prefix length" in KMP) parlance)\n* number of odd or even values\n  * state: the number of odd or even values so far\n\nIn all of these cases, the trick is to record *just enough* state information to get the right answer, but without adding so many DP/top-down DFS cache entries that you get TLE/MLE.\n\n## KMP\n\nToo involved for this post. But some pointers:\n* the code I write is a canonical KMP table, and the "`kk` fallback" is a canonical loop in normal KMP\n* `F[i]` means "if we fail to match `pattern[i]` with the next character, try `pattern[F[i]]` next\n\nKMP in my opinion is an example of a "space aliens" algorithm: it *looks* simple, but it\'s actually a very clever hybrid of two-pointer (index `i` and prefix `p`) AND dynamic programming (`F[p]` table). So it\'s basically for space aliens in the sense that I doubt anyone derives KMP in an interview ever.\n\nAt least to me, KMP is hard. But I force myself to use it and review it regularly so I can use it in interviews without failing.\n\n# Complexity\n- Time complexity: `O(n*len(evil))`. We can read the complexity off the top-down DFS function arguments. We have two booleans for O(1) states, `i` for `O(n)` values, and `k` for `O(len(evil))` values. In the worst case we fill out the entire table. In the best case, the common prefix of s1 and s2 contain `evil` so we return 0 rather quickly.\n\n- Space complexity: `O(n*len(evil))`. We can read off the function arguments to see that this is the maximum number of cache entries we\'ll have.\n\n# Code\n```\nclass Solution:\n    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n        # good string\n        #   size n\n        #   lex >= s1\n        #   lex <= s2\n        #   does NOT contain evil\n\n        BIG = 10**9 + 7\n\n        # count of strings in [s1, s2] at index i:\n        #    if we\'ve matched s1 thus far, we have to pick a character at least s1[i]. Else anything.\n        #    if we\'ve matched s2 thus far, we have to pick a character at most s2[i]. Else anything.\n        #    If we match a character in evil, increment a pointer `k`,\n        #       the longest prefix of `evil` we\'ve matched so far (KMP!!)\n        #    NOTE: Not matching evil[k] does NOT mean the prefix resets!\n        #          It just means we have to backtrack in `evil` to find a shorter prefix\n        #          that matches. This is exactly what KMP does to speed up string matching,\n        #          hence why we need the KMP table.\n\n        # KMP table for evil\n        F = [-1]\n        p = -1\n        for i in range(1, len(evil)):\n            p += 1\n            if evil[i] == evil[p]:\n                F.append(F[p])\n            else:\n                F.append(p)\n                p = F[p]\n                while p > -1 and evil[p] != evil[i]:\n                    p = F[p]\n\n        def charsBetween(c1: chr, c2: chr) -> Iterator[chr]:\n            o1 = ord(c1)\n            o2 = ord(c2)\n            for o in range(o1, o2+1):\n                yield chr(o)\n\n        @cache\n        def countBetween(m1: bool, m2: bool, i: int, k: int) -> int:\n            """\n            Returns the number of ways we can pick indices i: of strings between s1 and s2\n            given that the next character in `evil` we must dodge is at index `k`\n\n            @param m1: if the preceeding characters match s1\n            @param m2: if the preceeding characters match s2\n            """\n\n            if k == len(evil): return 0 # we have a copy of evil now\n\n            if i == n: return 1 # empty string to finish\n\n            l = s1[i] if m1 else \'a\' # lowest we can pick without dropping below s1\n            r = s2[i] if m2 else \'z\' # highest .................. going above s2\n\n            ans = 0\n            for c in charsBetween(l, r): # try all characters in [l, r]\n                # k means we\'ve matched :k in evil\n                # if evil[kk] == k, we match and increment k\n                # if not, backtrack with KMP table as usual\n                # This lets us account for the fact that we may not\n                # match evil[k], but the prior `k` characters may\n                # match a long suffix, and thus kk > 0. Otherwise\n                # we\'d be fooled into thinking a match to evil is\n                # impossible\n                kk = k\n                while kk > -1 and evil[kk] != c:\n                    kk = F[kk]\n                kk += 1\n\n                ans += countBetween(m1 and c == l, m2 and c == r, i+1, kk)\n\n            return ans % BIG\n\n        # initial conditions:\n        #     current string is the empty string, which matches s1[:0] and s2[:0]. Hence True, True\n        #     next index to pick for the string is 0\n        #     next index in evil is 0\n        return countBetween(True, True, 0, 0)\n```
['Python3']