Algorithms
Hard
2781
2884
Length of the Longest Valid Substring
length-of-the-longest-valid-substring
"""
You are given a string word and an array of strings forbidden.

A string is called valid if none of its substrings are present in forbidden.

Return the length of the longest valid substring of the string word.

A substring is a contiguous sequence of characters in a string, possibly empty.

Example 1:

Input: word = "cbaaaabc", forbidden = ["aaa","cb"]
Output: 4
Explanation: There are 11 valid substrings in word: "c", "b", "a", "ba", "aa", "bc", "baa", "aab", "ab", "abc" and "aabc". The length of the longest valid substring is 4.
It can be shown that all other substrings contain either "aaa" or "cb" as a substring.

Example 2:

Input: word = "leetcode", forbidden = ["de","le","e"]
Output: 4
Explanation: There are 11 valid substrings in word: "l", "t", "c", "o", "d", "tc", "co", "od", "tco", "cod", and "tcod". The length of the longest valid substring is 4.
It can be shown that all other substrings contain either "de", "le", or "e" as a substring.


Constraints:

 * 1 <= word.length <= 105
 * word consists only of lowercase English letters.
 * 1 <= forbidden.length <= 105
 * 1 <= forbidden[i].length <= 10
 * forbidden[i] consists only of lowercase English letters.
"""
class Solution:
    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
        
You are given a string word and an array of strings forbidden.

A string is called valid if none of its substrings are present in forbidden.

Return the length of the longest valid substring of the string word.

A substring is a contiguous sequence of characters in a string, possibly empty.

Example 1:

Input: word = "cbaaaabc", forbidden = ["aaa","cb"]
Output: 4
Explanation: There are 11 valid substrings in word: "c", "b", "a", "ba", "aa", "bc", "baa", "aab", "ab", "abc" and "aabc". The length of the longest valid substring is 4.
It can be shown that all other substrings contain either "aaa" or "cb" as a substring.

Example 2:

Input: word = "leetcode", forbidden = ["de","le","e"]
Output: 4
Explanation: There are 11 valid substrings in word: "l", "t", "c", "o", "d", "tc", "co", "od", "tco", "cod", and "tcod". The length of the longest valid substring is 4.
It can be shown that all other substrings contain either "de", "le", or "e" as a substring.


Constraints:

 * 1 <= word.length <= 105
 * word consists only of lowercase English letters.
 * 1 <= forbidden.length <= 105
 * 1 <= forbidden[i].length <= 10
 * forbidden[i] consists only of lowercase English letters.


Please complete the code below to solve above prblem:
```python
class Solution:
    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
        
```

my_solution = Solution()

test_input = { "word": "cbaaaabc", "forbidden": ["aaa","cb"] }
assert my_solution.longestValidSubstring(**test_input) == 4

test_input = { "word": "leetcode", "forbidden": ["de","le","e"] }
assert my_solution.longestValidSubstring(**test_input) == 4

test_input = { "word": "a", "forbidden": ["n"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "a", "forbidden": ["s"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "a", "forbidden": ["a"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "b", "forbidden": ["g"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "b", "forbidden": ["t"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "b", "forbidden": ["b"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "c", "forbidden": ["k"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "c", "forbidden": ["s"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "c", "forbidden": ["c"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "d", "forbidden": ["h"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "d", "forbidden": ["n"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "d", "forbidden": ["d"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "e", "forbidden": ["s"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "e", "forbidden": ["e"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "f", "forbidden": ["b"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "f", "forbidden": ["s"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "f", "forbidden": ["f"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "g", "forbidden": ["r"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "g", "forbidden": ["y"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "g", "forbidden": ["g"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "h", "forbidden": ["v"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "h", "forbidden": ["b"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "h", "forbidden": ["h"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "i", "forbidden": ["k"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "i", "forbidden": ["y"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "i", "forbidden": ["i"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "j", "forbidden": ["v"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "j", "forbidden": ["u"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "j", "forbidden": ["j"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "k", "forbidden": ["z"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "k", "forbidden": ["o"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "k", "forbidden": ["k"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "l", "forbidden": ["i"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "l", "forbidden": ["r"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "l", "forbidden": ["l"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "m", "forbidden": ["s"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "m", "forbidden": ["g"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "m", "forbidden": ["m"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "n", "forbidden": ["e"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "n", "forbidden": ["i"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "n", "forbidden": ["n"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "o", "forbidden": ["j"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "o", "forbidden": ["f"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "o", "forbidden": ["o"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "p", "forbidden": ["z"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "p", "forbidden": ["i"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "p", "forbidden": ["p"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "q", "forbidden": ["j"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "q", "forbidden": ["z"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "q", "forbidden": ["q"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "r", "forbidden": ["v"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "r", "forbidden": ["p"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "r", "forbidden": ["r"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "s", "forbidden": ["m"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "s", "forbidden": ["x"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "s", "forbidden": ["s"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "t", "forbidden": ["v"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "t", "forbidden": ["m"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "t", "forbidden": ["t"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "u", "forbidden": ["l"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "u", "forbidden": ["n"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "u", "forbidden": ["u"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "v", "forbidden": ["o"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "v", "forbidden": ["v"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "w", "forbidden": ["w"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "w", "forbidden": ["s"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "x", "forbidden": ["r"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "x", "forbidden": ["q"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "x", "forbidden": ["x"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "y", "forbidden": ["w"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "y", "forbidden": ["t"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "y", "forbidden": ["y"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "z", "forbidden": ["l"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "z", "forbidden": ["o"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "z", "forbidden": ["z"] }
assert my_solution.longestValidSubstring(**test_input) == 0

test_input = { "word": "acbc", "forbidden": ["cbc","acb","acb","acbc"] }
assert my_solution.longestValidSubstring(**test_input) == 2

test_input = { "word": "cabba", "forbidden": ["aaba","abba","acabb","cabb"] }
assert my_solution.longestValidSubstring(**test_input) == 3

test_input = { "word": "bbc", "forbidden": ["baba","babc","bbc","bbc"] }
assert my_solution.longestValidSubstring(**test_input) == 2

test_input = { "word": "acb", "forbidden": ["acb","caccc","baaab","baa"] }
assert my_solution.longestValidSubstring(**test_input) == 2

test_input = { "word": "aaac", "forbidden": ["aaac","aac","aaa","aaac"] }
assert my_solution.longestValidSubstring(**test_input) == 2

test_input = { "word": "ca", "forbidden": ["ababa","ca","caac","babb"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "babbb", "forbidden": ["bbb","aacb","babbb","bcab"] }
assert my_solution.longestValidSubstring(**test_input) == 4

test_input = { "word": "cbbba", "forbidden": ["bca","cbbba","acbcc","aabb"] }
assert my_solution.longestValidSubstring(**test_input) == 4

test_input = { "word": "abab", "forbidden": ["aab","abab","cacb","bab"] }
assert my_solution.longestValidSubstring(**test_input) == 3

test_input = { "word": "cbab", "forbidden": ["bbcc","aaccc","cbab","babca"] }
assert my_solution.longestValidSubstring(**test_input) == 3

test_input = { "word": "caaa", "forbidden": ["aaa","cbb","aaa","caaa"] }
assert my_solution.longestValidSubstring(**test_input) == 3

test_input = { "word": "baa", "forbidden": ["aaab","bbaa","babac","baa"] }
assert my_solution.longestValidSubstring(**test_input) == 2

test_input = { "word": "cbcc", "forbidden": ["cbcc","baa","bbba","cac"] }
assert my_solution.longestValidSubstring(**test_input) == 3

test_input = { "word": "cac", "forbidden": ["cccaa","baaca","cac","cac"] }
assert my_solution.longestValidSubstring(**test_input) == 2

test_input = { "word": "cabab", "forbidden": ["cabab","abab","cabab","abab"] }
assert my_solution.longestValidSubstring(**test_input) == 4

test_input = { "word": "caa", "forbidden": ["caa","bba","acc","bcabb"] }
assert my_solution.longestValidSubstring(**test_input) == 2

test_input = { "word": "ba", "forbidden": ["ba","ba","cab","cbcac"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "bbc", "forbidden": ["baca","bbc","bbc","caa"] }
assert my_solution.longestValidSubstring(**test_input) == 2

test_input = { "word": "bbb", "forbidden": ["cbaab","bbb","bbb","bab"] }
assert my_solution.longestValidSubstring(**test_input) == 2

test_input = { "word": "bbccc", "forbidden": ["ccc","bcba","bcc","bcc"] }
assert my_solution.longestValidSubstring(**test_input) == 3

test_input = { "word": "bcac", "forbidden": ["bcac","caca","bcac","bca"] }
assert my_solution.longestValidSubstring(**test_input) == 3

test_input = { "word": "ab", "forbidden": ["aca","cabcc","caba","ab"] }
assert my_solution.longestValidSubstring(**test_input) == 1

test_input = { "word": "caa", "forbidden": ["bab","babbb","abbaa","caa"] }
assert my_solution.longestValidSubstring(**test_input) == 2