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

from collections import deque
class Trie:
    def __init__(self):
        self.root = dict()
    
    def insert(self, s):
        cnode = self.root
        for i,c in enumerate(s):
            if c not in cnode:
                cnode[c] = dict()
            cnode = cnode[c]
            if i == len(s) - 1:
                cnode[""] = True
    
    def find(self, s):
        cnode = self.root
        for i,c in enumerate(s):
            if c not in cnode:
                return -1
            cnode = cnode[c]
            if "" in cnode:
                return i 
        
        return -1
        
            
class Solution:
    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
        # 1. 트라이 구현
        trie = Trie()

        # 2. 트라이에 forbidden 저장
        for s in forbidden:
            trie.insert(s)
        
        # 3. word 0 ~ -1, 1 ~ -1, ... , len(word) - 2 ~ -1까지 트라이에 넣어서 구간 리스트에 저장
        forbidden_ranges = []
        for start in range(len(word)):
            idx = trie.find(word[start:])
            if idx != -1:
                forbidden_ranges.append([start, start + idx])
        q = deque(forbidden_ranges)
        q2 = deque()
        while q:
            if q2:
                if q2[-1][1] >= q[0][1]:
                    q2.pop()
            q2.append(q.popleft())
        # 4. left, right 놓고 사이에 forbidden 있으면 left++ 없으면 최대값 업데이트 후 right ++
        ans = 0
        left = 0
        right = 0
        idx = 0
        q = q2
        while right < len(word):
            
            if q:
                while q[0][0] < left:
                    q.popleft()
                    if not q:
                        break
            if q:
                if q[0][1] <= right:
                    left += 1
                    continue     
            ans = max(ans, right - left + 1)
            right += 1
        return ans
161900