<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:
        currTrie = Trie()
        minLen = math.inf
        maxLen = -math.inf
        for w in forbidden:
            currTrie.insert(w[::-1])
            minLen = min(minLen, len(w))
            maxLen = min(maxLen, len(w))

        def dfs(currNode, currIndex):
            if currNode.word:
                return (True, currIndex+1)
            if currIndex < 0 or word[currIndex] not in currNode.children:
                return (False, currIndex)

            return dfs(currNode.children[word[currIndex]], currIndex-1)

        
        n = len(word)
        longestValidLen = 0
        left = -1
        for i in range(n):
            # print(i)
            if word[i] in currTrie.trie.children:
                wordFound, lastIndex = dfs(currTrie.trie.children[word[i]], i-1)
                if wordFound:
                    left = max(left, lastIndex)
                # print('flag', wordFound, lastIndex, left)

            longestValidLen = max(longestValidLen, i-left)
            # print('longest', longestValidLen)

        return longestValidLen
                    
                    
class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = False

class Trie:
    def __init__(self):
        self.trie = TrieNode()
    
    def insert(self, word):
        currNode = self.trie
        for ch in word:
            if ch not in currNode.children:
                currNode.children[ch] = TrieNode()
            currNode = currNode.children[ch]

        currNode.word = True


    def searchWord(self, word):
        currNode = self.trie
        for ch in word:
            if ch not in currNode.children:
                return False
            currNode = currNode.children[ch]
        
        if currNode.word:
            return True
        return False
    
    def startsWith(self, prefix):
        currNode = self.trie
        for ch in prefix:
            if ch not in currNode.children:
                return False
            currNode = currNode.children[ch]
        
        return True
        
2481