<p>You are given a string <code>word</code> and an array of strings <code>forbidden</code>.</p>

<p>A string is called <strong>valid</strong> if none of its substrings are present in <code>forbidden</code>.</p>

<p>Return <em>the length of the <strong>longest valid substring</strong> of the string </em><code>word</code>.</p>

<p>A <strong>substring</strong> is a contiguous sequence of characters in a string, possibly empty.</p>

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

<pre>
<strong>Input:</strong> word = &quot;cbaaaabc&quot;, forbidden = [&quot;aaa&quot;,&quot;cb&quot;]
<strong>Output:</strong> 4
<strong>Explanation:</strong> There are 11 valid substrings in word: &quot;c&quot;, &quot;b&quot;, &quot;a&quot;, &quot;ba&quot;, &quot;aa&quot;, &quot;bc&quot;, &quot;baa&quot;, &quot;aab&quot;, &quot;ab&quot;, &quot;abc&quot; and &quot;aabc&quot;. The length of the longest valid substring is 4. 
It can be shown that all other substrings contain either &quot;aaa&quot; or &quot;cb&quot; as a substring. </pre>

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

<pre>
<strong>Input:</strong> word = &quot;leetcode&quot;, forbidden = [&quot;de&quot;,&quot;le&quot;,&quot;e&quot;]
<strong>Output:</strong> 4
<strong>Explanation:</strong> There are 11 valid substrings in word: &quot;l&quot;, &quot;t&quot;, &quot;c&quot;, &quot;o&quot;, &quot;d&quot;, &quot;tc&quot;, &quot;co&quot;, &quot;od&quot;, &quot;tco&quot;, &quot;cod&quot;, and &quot;tcod&quot;. The length of the longest valid substring is 4.
It can be shown that all other substrings contain either &quot;de&quot;, &quot;le&quot;, or &quot;e&quot; as a substring. 
</pre>

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

<ul>
	<li><code>1 &lt;= word.length &lt;= 10<sup>5</sup></code></li>
	<li><code>word</code> consists only of lowercase English letters.</li>
	<li><code>1 &lt;= forbidden.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= forbidden[i].length &lt;= 10</code></li>
	<li><code>forbidden[i]</code> consists only of lowercase English letters.</li>
</ul>

"""
The key to this problem is recognizing/spotting that if i:j matches a string in forbidden, then that necessarily means i:j+1 and i:j+2 and so forth contains the substring i:j that is in forbidden.
It also means that i-1:j, i-2:j, and so forth contains the substring i:j that is in forbidden.
This key observation means that we can end our search early when expanding using one of the two indices.
I illustrated 4 types of 



Input: word = "cbaaaabc", forbidden = ["aaa","cb"]

# Check "c"
c   b   a   a   a   a   b   c   len     forbidden = ["aaa","cb"]
                            right
                            left
                            k
                                k + 1

# check "b"
c   b   a   a   a   a   b   c   len     forbidden = ["aaa","cb"]
                            right
                        left
                        k
                            k + 1   

# check "bc"
c   b   a   a   a   a   b   c   len     forbidden = ["aaa","cb"]
                            right
                        left
                            k
                                k + 1


# check "a"
c   b   a   a   a   a   b   c   len     forbidden = ["aaa","cb"]
                            right
                    left
                    k
                        k + 1


# check "ab"
c   b   a   a   a   a   b   c   len     forbidden = ["aaa","cb"]
                            right
                    left
                        k
                            k + 1    


# check "abc"
c   b   a   a   a   a   b   c   len     forbidden = ["aaa","cb"]
                            right
                    left
                            k
                                k + 1    


....

# check "aaa"
c   b   a   a   a   a   b   c   len     forbidden = ["aaa","cb"]
                    right
            left
                    k
                        k + 1    




# my version

# check "c"
c   b   a   a   a   a   b   c   len     forbidden = ["aaa","cb"]
    right
left
marker


# check "b"
c   b   a   a   a   a   b   c   len     forbidden = ["aaa","cb"]
        right
    left
marker


# check "cb"
c   b   a   a   a   a   b   c   len     forbidden = ["aaa","cb"]
        right
left
marker
                           



The lesson I learned is that there are 8 ways to perform dual-index iteration over a string. 
Think of the outer loop as a moving pivot or partition barrier "|". The inner loop can loop from: 
1. | to start
2. start to |
3. | to end
4. end to |
The pivot itself can move in 2 directions: front to back, or back to front. So the 4 ways to iterate the string become 8 ways total. 



But there are only 4 ways to perform dual-index iteration for this problem, because we need to expand outward from the pivot rather than start fully expanded and approach toward the pivot:

a   b   c   d   len

Iteration pattern 1: (i outer inc, j inner inc)
i   j
i       j
i           j
i               j
    i   j
    i       j
    i           j
        i   j
        i       j
            i   j 

Iteration pattern 2: (j outer inc, i inner dec )
i   j
    i   j
i       j
        i   j
    i       j
i           j
            i   j
        i       j
    i           j
i               j

Iteration pattern 3: (i outer dec, j inner inc)
            i   j
        i   j
        i       j
    i   j
    i       j
    i           j
i   j
i       j
i           j
i               j

Iteration pattern 4: (j outer dec, i inner dec)
            i   j
        i       j
    i           j
i               j
        i   j
    i       j
i           j
    i   j
i       j
i   j
"""


class Solution:
    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
        forbidden_set = set(forbidden)
        ans = 0

        start = 0
        for right in range(1, len(word) + 1):
            is_break = False

            # The reason for the -10 is the problem's constraints: 
            # 1 <= forbidden[i].length <= 10
            for left in range(right - 1, max(start, right - 10) - 1, -1): 
                if word[left:right] in forbidden_set:
                    start = left + 1
                    is_break = True
                    break
            if not is_break:
                ans = max(ans, right - start)
        return ans

    def longestValidSubstring_(self, word: str, forbidden: List[str]) -> int:
        forbidden_set = set(forbidden)
        ans = 0
        right = len(word)
        for left in range(len(word) - 1, -1, -1):
            for k in range(left + 1, min(left + 10, right) + 1):
                if word[left:k] in forbidden_set:
                    right = k - 1
                    break
            ans = max(ans, right - left)
        return ans

1122