<p>Given the strings <code>s1</code> and <code>s2</code> of size <code>n</code> and the string <code>evil</code>, return <em>the number of <strong>good</strong> strings</em>.</p>

<p>A <strong>good</strong> string has size <code>n</code>, it is alphabetically greater than or equal to <code>s1</code>, it is alphabetically smaller than or equal to <code>s2</code>, and it does not contain the string <code>evil</code> as a substring. Since the answer can be a huge number, return this <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 2, s1 = &quot;aa&quot;, s2 = &quot;da&quot;, evil = &quot;b&quot;
<strong>Output:</strong> 51 
<strong>Explanation:</strong> There are 25 good strings starting with &#39;a&#39;: &quot;aa&quot;,&quot;ac&quot;,&quot;ad&quot;,...,&quot;az&quot;. Then there are 25 good strings starting with &#39;c&#39;: &quot;ca&quot;,&quot;cc&quot;,&quot;cd&quot;,...,&quot;cz&quot; and finally there is one good string starting with &#39;d&#39;: &quot;da&quot;.&nbsp;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 8, s1 = &quot;leetcode&quot;, s2 = &quot;leetgoes&quot;, evil = &quot;leet&quot;
<strong>Output:</strong> 0 
<strong>Explanation:</strong> All strings greater than or equal to s1 and smaller than or equal to s2 start with the prefix &quot;leet&quot;, therefore, there is not any good string.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 2, s1 = &quot;gx&quot;, s2 = &quot;gz&quot;, evil = &quot;x&quot;
<strong>Output:</strong> 2
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>s1.length == n</code></li>
	<li><code>s2.length == n</code></li>
	<li><code>s1 &lt;= s2</code></li>
	<li><code>1 &lt;= n &lt;= 500</code></li>
	<li><code>1 &lt;= evil.length &lt;= 50</code></li>
	<li>All strings consist of lowercase English letters.</li>
</ul>

class Solution:
    # what is the range of values n can take on? [1, 500]
    # is len(s1) == len(s2) == len(evil) == n? yes, but len(evil) in [1, 50]
    # is s1 <= s2? yes
    # can evil equal s1? what about s2? probably
    # can any of the string inputs be a null reference? no
    # we are returning a count integer!
    # what characters are we dealing with? lowercase english letters? yes lowercase english letters
    # is the answer unique? yes
    # is the answer >= 0? yes
    # can evil be a substring of s1? think so

    # idea 0
    # brute force
    # create string builder copy of s1
    # for each letter of s1 (starting from right to left)
    #    for i in range(0,ord('z')-ord(currLetter)):
    #       add i to currLeter's ascii code
    #       if string builder as a joined string is less than s2 and doesn't contain evil
    #          add one to ans 

    # idea 1
    # dynamic programming to retrieve count
    # Objective function: dp(i) = number of good strings between s1 and s2 when
    #       altering just s1[i:]
    # base case: dp(n) = 0 because empty string is < s1
    # recurrence relation
    #     dp(i) = dp(i+1) + 
    #         (ord(s2[i]) - ord(s1[i])+1)
    # order: bottom up because we initially call dp(0) and work our way
    #      up to dp(n)
    # answer: dp(0)
    # optimization: hmmmm... maybe just use an iterative tabulation technique
    #      that stores dp(i+1)'s value inside a single variable
    # pseudocode
    # dp_cache = {}
    # def dp(i):
    #    if i == n:
    #        return 0
    #    if i in dp_cache:
    #        return dp_cache[i]
    #    res = ord(s2[i]) - ord(s1[i])+1
    #    res += dp(i+1)
    #    dp_cache[i] = res
    #    return res
    # return dp(0)
    
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        # implement idea 1 (memoized DP; bottom up) <<< doesn't work
        # dp_cache = {}
        # def dp(i):
        #     if i == n:
        #         return 0
        #     if i in dp_cache:
        #         return dp_cache[i]
        #     if evil in s1[:i]:
        #         dp_cache[i] = 0
        #         return 0
        #     res = 0
        #     upperbound = (ord(s2[i]) - ord(s1[i]) if i == 0 else 26)
        #     for j in range(0,upperbound+1):
        #         newString = s1[:i]+chr(ord('a')+j)#+s1[i+1:]
        #         if evil not in newString and s1[:i+1]<=newString <= s2[:i+1]:
        #             res+=1
        #     print(res)
        #     res *= dp(i+1)
        #     dp_cache[i] = res
        #     return res
        # return dp(0)

        # Fellow LeetCodian solution #1 (KMP + String DP)
        #   from https://leetcode.com/problems/find-all-good-strings/solutions/4926092/kmp-string-dp
        #    also check https://leetcode.com/problems/find-all-good-strings/solutions/4779922/python-3-top-down-dfs-with-caching-and-kmp
        e = len(evil)
        kmp = [0]*e
        # ^^^ NOTE: kmp[i] stores the length (equal to j MAYBE plus 1) of 
        #     the longest prefix of 'evil' that equals a suffix of evil[:i+1]
        #     where j < i.
        j = 0
        for i in range(1,e): # O(E)
            while j > 0 and evil[i]!=evil[j]: # O(E)
                # evil[i] does not match character at j
                #  so let us update j to the
                #  length of the longest prefix of 'evil' that equals
                #  a suffix of evil[:j]
                j = kmp[j-1]
            # at this point, j == 0 or evil[i] == evil[j]
            if evil[i] == evil[j]:
                # evil[i] == evil[j], so we must 
                #    increment j so that j is a length
                #    instead of a 0-based index
                j+=1
            kmp[i] = j
        dp_cache = {}
        def dp(i,j,tight1,tight2):
            '''
            - i = index of next character we must tack on to our constructed string
            - j = max length of common prefix between our current state of our constructed string and evil
            - tight1 = true iff prefix of our current state of our constructed string
                is a prefix of s1. If true, the char we put here cannot be less than s1[i]
            - tight2 = true iff the prefix of our current state of our constructed string is a prefix of s2. If true, the char we put here cannot be greater than s2[i]
            '''
            if (i,j,tight1,tight2) in dp_cache:
                return dp_cache[(i,j,tight1,tight2)]
            if j == e:
                # we have a copy of evil now
                #   because we cannot build any string
                #   beginning with current prefix.
                # This basically means our constructed string
                #   contains evil as a substring (no-no)
                # Return zero to ignore our constructed string
                return 0
            if i == n:
                # Our constructed string finally has size n
                #   which means our constructed string,
                #   at this point, is a good string.
                # Return one to count our constructed string
                return 1
            # get lowest ASCII code we can pick without dropping below s1
            lo = ord('a') if not tight1 else ord(s1[i])
            # get highets ASCII code we can pick without going above s2
            hi = ord('z') if not tight2 else ord(s2[i])
            res = 0
            # use 'kmp' array to find the
            #    longest common prefix
            #    between evil and the currently
            #    constructed string that is greater than
            #    s1 and is of length i+1
            for k in range(lo,hi+1):
                newLetter = chr(k)
                nj = j
                while nj>0 and evil[nj]!=newLetter:
                    nj = kmp[nj-1]
                if newLetter == evil[nj]:
                    nj+=1
                if nj<e:
                    res += (
                        dp(
                            # move on to next index of our constructed string
                            i+1,
                            # pass in max length of common prefix between our current state of our constructed string and evil
                            nj,
                            # check if k helps build another prefix of s1
                            tight1 and (k==lo),
                            # check if k helps build another prefix of s2
                            tight2 and (k==hi)
                        )
                    )
            dp_cache[(i,j,tight1,tight2)] = res
            return res
        return dp(0,0,True,True) % (10**9 + 7)
        # Time = O(3E + 2*2*N*E) = O(N*E) for building the kmp array
        #    and filling the dp_cache
        # Memory = O(N + N*E) = O(N*E) for the max recursion depth and the dp_cache

        
24800