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

'''
Input:
str word, List[str] forbidden_substring_list

Output:
int length_of_longest_valid_substring

Constraints:
- Q1: Can input be empty? A: Yes
- Q2: What is the alphabet set of word, forbidden_substring_list[i]? A: [a-z]
- Q3: What is len(word), len(forbidden_substring_list)? A: 1 ~ 10^5
- Q4: What is len(forbidden_substring_list[i])? Can it be empty string ""? A: No. 1 ~ 10

Test Cases:
word = "cbaaaabc", forbidden = ["aaa","cb"], return 4 ("aabc")
word = "leetcode", forbidden = ["de","le","e"], return 4 ("tcod")

[Solution 1: Hashmap + Two Pointers - Same Direction]
Idea:
# forbidden_set = set(forbidden_substring_list)
# res = 0
# j = n - 1

# MAX_FORBIDDEN_SUBSTRING_LENGTH = 10
# for i = n - 1....0
# - for k = i...min(i + MAX_FORBIDDEN_SUBSTRING_LENGTH, j) 
# --- if word[i:k + 1] in forbidden_set:
# ----- j = i - 1
# ----- break
# - res = max(res, j - i + 1)

Time: O(max_forbidden_substring_length^2 * n)
Space: O(forbidden_substring_set)
'''


class Solution1:
    def longestValidSubstring(self, word: str, forbidden_substring_list: set[str]) -> int:# res = 0
        n = len(word)
        
        # forbidden_set = set(forbidden_substring_list)
        forbidden_set = set(forbidden_substring_list)
        
        # res = 0
        res = 0
        
        # j = n - 1
        j = n - 1
        
        # MAX_FORBIDDEN_SUBSTRING_LENGTH = 10
        # for i = n - 1....0
        # - for k = i...min(i + MAX_FORBIDDEN_SUBSTRING_LENGTH, j) 
        # --- if word[i:k + 1] in forbidden_set:
        # ----- j = i - 1
        # ----- break
        # - res = max(res, j - i + 1)
        MAX_FORBIDDEN_SUBSTRING_LENGTH = 10
        for i in range(n - 1, -1, -1):
            for k in range(i, min(i + MAX_FORBIDDEN_SUBSTRING_LENGTH, j) + 1):
                if word[i:k+1] in forbidden_set:
                    j = k - 1
                    break
            res = max(res, j - i + 1)
        
        # return res
        return res
    

class Solution:
    def longestValidSubstring(self, word: str, forbidden_substring_list: List[str]) -> int:
        n = len(word)
        forbidden_set = set(forbidden_substring_list)
        res = 0
        j = 0

        for i in range(n):
            while j < n and not self.has_forbidden_substring(word, i, j, forbidden_set):
                j += 1
            
            res = max(res, j - i)
        
        return res


    def __init__(self):
        self.MAX_FORBIDDEN_SUBSTRING_LENGTH = 10
    

    def has_forbidden_substring(self, word: str, i: int, j: int, forbidden_set: set[str]) -> bool:
        for k in range(max(i, j - 9), j + 1):
            if word[k:j+1] in forbidden_set:
                return True
        return False
1660