2781. Length of the Longest Valid Substring Hard

1/**
2 * [2781] Length of the Longest Valid Substring
3 *
4 * You are given a string word and an array of strings forbidden.
5 * A string is called valid if none of its substrings are present in forbidden.
6 * Return the length of the longest valid substring of the string word.
7 * A substring is a contiguous sequence of characters in a string, possibly empty.
8 *  
9 * <strong class="example">Example 1:
10 * 
11 * Input: word = "cbaaaabc", forbidden = ["aaa","cb"]
12 * Output: 4
13 * 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. 
14 * It can be shown that all other substrings contain either "aaa" or "cb" as a substring. 
15 * <strong class="example">Example 2:
16 * 
17 * Input: word = "leetcode", forbidden = ["de","le","e"]
18 * Output: 4
19 * 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.
20 * It can be shown that all other substrings contain either "de", "le", or "e" as a substring. 
21 * 
22 *  
23 * Constraints:
24 * 
25 * 	1 <= word.length <= 10^5
26 * 	word consists only of lowercase English letters.
27 * 	1 <= forbidden.length <= 10^5
28 * 	1 <= forbidden[i].length <= 10
29 * 	forbidden[i] consists only of lowercase English letters.
30 * 
31 */
32pub struct Solution {}
33
34// problem: https://leetcode.com/problems/length-of-the-longest-valid-substring/
35// discuss: https://leetcode.com/problems/length-of-the-longest-valid-substring/discuss/?currentPage=1&orderBy=most_votes&query=
36
37// submission codes start here
38
39impl Solution {
40    pub fn longest_valid_substring(word: String, forbidden: Vec<String>) -> i32 {
41        0
42    }
43}
44
45// submission codes end
46
47#[cfg(test)]
48mod tests {
49    use super::*;
50
51    #[test]
52    fn test_2781() {
53    }
54}
55