<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:
        
        n = len(word)
        
        aux = []
        
        lns = [False]*11
        
        st = set()
        
        for z in forbidden:
            
            l = len(z)
            
            if z not in st:
            
                aux.append([l, z])

                st.add(z)
            
            lns[l] = True
        
        for l, z in aux:
            
            if z not in st:
                continue 
            
            for k in range(l-1):
                
                if not lns[k+1]:
                    continue
                
                flag = False 
                
                var = []
                
                for i in range(k+1):
                    var.append(z[i])
                    
                if ''.join(var) in st:
                    st.remove(z)
                    break 
                
                for j in range(k+1, l):
                    var.pop(0)
                    var.append(z[j])
                    
                    if ''.join(var) in st:
                        flag = True 
                        break 
                        
                if flag:
                    st.remove(z)
                    break 
            
        ans = 0 
        curr = 0 
        i = 0 
        
        while i < n:
            z = word[i]
                
            flag = False

            for j in range(10):
                if i+j >= n:
                    break

                if word[i:i+j+1] in st:
                    flag = True 
                    break 

            if not flag:
                curr += 1 
                i += 1 
                ans = max(ans, curr)
            else:
                ans = max(ans, curr+j)
                i += 1
                curr = 0 
                 
        return ans
41900