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

    """
    Brute force

    Consider each substring in a word => S
    Within the substring S, we also need to consider multiple substrings to check if it's valid i.e 
    not present in forbidden list of strings

    for i in range(len(word)):
        for j in range(i, len(word)):
            S = word[i:j+1] # substring
            if isValid(S, forbidden):
                calculateMaxLength(S, max_len)

    How to check if isValid(S, forbidden) ?

    Check if 


    len(word) = N
    len(forbidden) = F, average len forbidden word = FL <= 10
    len(average word) = n
    N^2 * (costs of substring + isValid check)

    isValid time complexity is N^2 as well 
    N^2 * N^2 * (...) 

    N^4 for brute force 
    Space complexity is storing forbidden set, creating the substrings

    A lot of duplicate checks involved...
    1. isValid check from left to right, if [left:right'] is invalid, then [left:right+1] is also invalid
    2. so we can terminate early if substring encounter is wrong 

    """
    def longestValidSubstringBruteForce(self, word: str, forbidden: List[str]) -> int:
        forbidden_set = set(forbidden)
        def isValid(word, forbidden):
            for l in range(len(word)):
                for r in range(l, len(word)):
                    if word[l:r+1] in forbidden:
                        return False
            return True
        longest_len = 0
        for i in range(len(word)):
            for j in range(i, len(word)): # We can optimise this step if word[i:j] is invalid, no need to check word[i:j+1]
                substring = word[i:j+1]
                # check if valid substring by seeing if every substring within S is not in forbidden list
                if isValid(substring, forbidden_set):
                    longest_len = max(longest_len, len(substring))
        return longest_len
        
    """
    Optimise isValid check
    1. FL <= 10 so we don't have to check longer than this length
    2. word[i:j] is invalid, no need to check word[i:j+1] onwards
    Introduction of j means we introduce a couple of new substrings to a valid one
    word[i:j], word[i+1:j], word[i+2:j] ... word[j-1:j] 

    N^2 * FL * (construct subsring + check in forbidden set) still TLE 
    """
    def longestValidSubstringImp(self, word: str, forbidden: List[str]) -> int:
        forbidden_set = set(forbidden)
        longest_len = 0
        for i in range(len(word)):
            for j in range(i, len(word)): # We can optimise this step if word[i:j] is invalid, no need to check word[i:j+1]
                # check for only the newly added substrings
                right = j
                is_valid = True
                for left in range(right, max(i-1, right-10), -1): # how far out newly added substrings we need to check is capped to 10 O(FL)
                    new_added_substring = word[left:right+1]
                    if new_added_substring in forbidden_set:
                        is_valid = False
                        break
                if not is_valid:
                    break
                else:
                    longest_len = max(longest_len, j - i + 1)
        return longest_len
    
    def longestValidSubstringT(self, word: str, forbidden: List[str]) -> int:
        forbidden_set = set(forbidden)
        longest_len = valid_left_bound = 0
        for right in range(len(word)): # expand right window
            # check backwards to see if 
            for left in range(max(valid_left_bound, right-10), right+1): # check 10 characters back, or until the most valid left bound
                if word[left:right+1] in forbidden_set: # encounter invalid here
                    valid_left_bound = left + 1
            longest_len = max(longest_len, right - valid_left_bound + 1)
        return longest_len

    

    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
        # insert Trie nodes
        trie = Trie()
        for forbidden_word in forbidden:
            trie.insert(forbidden_word)
        
        # precompute the array
        arr = [0] * len(word)
        for i in range(len(word)):
            substring = word[i:i+10]
            index_match = trie.matching(substring)
            if index_match == -1: # no match to forbidden word
                arr[i] = len(word) - 1 
            else:
                arr[i] = i + index_match - 1

        longest_len = 0
        left = 0
        while left < len(word):
            actual_right_bound = possible_right_bound = arr[left]
            l = left
            while l <= actual_right_bound:
                actual_right_bound = min(actual_right_bound, arr[l])
                l += 1
            longest_len = max(longest_len, actual_right_bound - left + 1)
            left = max(left+1, actual_right_bound-10)
        return longest_len


class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        current_node = self.root
        for c in word:
            current_node = current_node.children[c]
        current_node.is_end = True

    def matching(self, word):
        current_node = self.root
        for i, c in enumerate(word):
            current_node = current_node.children[c]
            if current_node.is_end: # match a forbidden word at index i
                return i
        return -1
2680