Watch 10 video solutions for Length of the Longest Valid Substring, a hard level problem involving Array, Hash Table, String. This walkthrough by Algorithms Made Easy has 54,894 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 105word consists only of lowercase English letters.1 <= forbidden.length <= 1051 <= forbidden[i].length <= 10forbidden[i] consists only of lowercase English letters.