<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>

# class Solution:
#     def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
#         result = self.findSubstring([word], forbidden)
#         return max([len(x) for x in result]) if result else 0


#     def findSubstring(self, words, forbidden):
#         # result = []
#         for forb in forbidden:
#             allow = []
#             for word in words:
#                 validStrings = self.findValid(word, forb)
#                 allow = allow + validStrings
#             words = allow

#         return words

#     def findValid(self, word, forb):
#         valids = []
#         while word:
#             index = word.find(forb)
#             if index >= 0:
#                 end = index + len(forb) - 1
#                 valids.append(word[:end])
#                 word = word[index + 1:]
#             else:
#                 valids.append(word)
#                 break
#         return valids


# class Solution:
#     def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
#         maxlen = 0
#         right = 0
#         left = 0
#         forbids = set(forbidden)
#         lengths = sorted([len(w) for w in forbidden])
#         # print(lengths)
#         while right < len(word):
#             nextLeft = left
#             for forbLen in lengths:
#                 if right + 1 - forbLen >= left and word[right + 1 - forbLen: right + 1] in forbids:
#                     nextLeft = max(nextLeft, right + 1 - forbLen + 1)
#                     # print('right=', right, 'nextLeft=', nextLeft, 'forbid=', word[right + 1 - forbLen: right + 1])
#                     break

#             left = nextLeft
#             maxlen = max(maxlen, right - left + 1)
#             right += 1

#         return maxlen


# class Solution:
#     def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
#         maxlen = 0
#         right = 0
#         left = 0
#         forbids = set(forbidden)
#         # lengths = sorted([len(w) for w in forbidden])
#         while right < len(word):
#             nextLeft = left
#             for forbLen in range(1, 11):
#                 if right + 1 - forbLen >= left and word[right + 1 - forbLen: right + 1] in forbids:
#                     nextLeft = max(nextLeft, right + 1 - forbLen + 1)
#                     break

#             left = nextLeft
#             maxlen = max(maxlen, right - left + 1)
#             right += 1

#         return maxlen


# class Solution:
#     def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
#         maxlen = 0
#         left = 0
#         right = 0
#         wl = 10
#         for w in forbidden:
#             wl = min(wl, len(w))

#         while right < len(word):
#             maxright = min(right + wl - 1, len(word) - 1)
#             # print('\n left', left, '  right', right, '  word[right]', word[right],  '  maxright', maxright)
#             violate = False
#             for forb in forbidden:
#                 if right + len(forb) - 1 < len(word):
#                     if word[right:].startswith(forb):
#                         maxright = min(maxright, right + len(forb) - 2)
#                         # print('  forb', forb, '  maxright', maxright)
#                         violate = True
                        
#             maxlen = max(maxlen, maxright - left + 1)
#             # print('\t maxlen', maxlen)

#             if maxright <= right:
#                 right += 1
#             else:
#                 right = maxright
            
#             if violate:
#                 left = right

#         return maxlen


# class Solution:
#     def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
#         maxlen = 0
#         left = right = 0

#         wl = 0
#         for forb in forbidden:
#             wl = max(wl, len(forb))

#         while right < len(word):
#             # print('\n######## ')

#             for forb in forbidden:
                
#                 if right - len(forb) + 1 >= left and word[right - len(forb) + 1:right+1]== forb:
#                     # print('right', right , '; prev left', left,  '; move to left', right - len(forb) + 2, '; maxlen', maxlen)
#                     left = max(left, right - len(forb) + 2)
                    
#                     # break

            
#             right += 1
#             maxlen = max(right - left, maxlen)
#             # print('right', right, '; maxlen', maxlen)
            
#         return maxlen


class Solution:
    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
        maxlen = 0
        left = right = 0

        wl = 0
        for forb in forbidden:
            wl = max(wl, len(forb))

        forbiddenset = set(forbidden)
        while right < len(word):
            # print('\n######## ')

            for l in range(1, wl+1):
                
                if right - l + 1 >= left and word[right - l + 1:right+1] in forbiddenset:
                    # print('right', right , '; prev left', left,  '; move to left', right - len(forb) + 2, '; maxlen', maxlen)
                    left = max(left, right - l + 2)
                    
                    # break

            
            right += 1
            maxlen = max(right - left, maxlen)
            # print('right', right, '; maxlen', maxlen)
            

        return maxlen

1802