<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:
        forbidden = set(forbidden)
        T = Trie()
        for f_word in forbidden:
            T.add(f_word)
        if all(c in T.root.sons and \
            T.root.sons[c].is_word for c in set(word)): 
            return 0 
        start = 0
        res = 0
        invalid = lambda d: any(v.is_word for v in d.values())
        d = dict()
        for end, c in enumerate(word):
            d = self.update_forward(d, start, end, c, T)
            if invalid(d):
                i = max(k for k in d.keys() if d[k].is_word)
                start = i+1
                d = {k: d[k] for k in d if k >= start}
            res = max(res, end-start+1)
        return res


    def update_forward(self, d, start, end, c, T):
        new_d = dict()
        if c in T.root.sons:
            new_d[end] = T.root.sons[c]
        for i, node in d.items():
            if i < start: continue
            if node.is_word:
                new_d[i] = node
            elif c in node.sons:
                new_d[i] = node.sons[c]
        return new_d                     
    def bisect():
        forbidden = set(forbidden)
        T = Trie()
        for f_word in forbidden:
            T.add(f_word)
        if all(c in T.root.sons and \
            T.root.sons[c].is_word for c in set(word)): 
            return 0            
        l, r = 1, len(word)
        res = 0
        while l <= r:
            mid = (l+r) // 2
            if self.has_sub(word, T, mid):
                l = mid+1
                res = max(res, mid)
            else:
                r = mid-1
        return res
    
    def has_sub(self, word, T, n):
        d = dict()
        start = 0
        for end, c in enumerate(word):
            #print(d)
            if end-start >= n:
                start += 1
            d = self.update_forbidden(d, start, end, c, T, n)
            if end-start == n-1 and not any(v.is_word for v in d.values()): return True
        return False

            
    def update_forbidden(self, d, start, end, c, T, n):
        new_d = dict()
        if c in T.root.sons:
            new_d[end] = T.root.sons[c]
        for i, node in d.items():
            if end-i >= n: continue
            if node.is_word:
                new_d[i] = node
            elif c in node.sons:
                new_d[i] = node.sons[c]
        return new_d

class Node:
    def __init__(self, c):
        self.c = c
        self.sons = dict()
        self.is_word = False
class Trie:
    def __init__(self):
        self.root = Node(None)
    def add(self, word):
        v = self.root
        for c in word:
            if c not in v.sons:
                v.sons[c] = Node(c)
            v = v.sons[c]
        v.is_word = True
    def find(self, word):
        v = self.root
        for c in word:
            if c not in v.sons: return False
            v = v.sons[c]
        return v.is_word

         
2481