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.The sliding window approach involves maintaining two pointers to track the substring that is currently being evaluated. By adjusting these pointers, you can efficiently evaluate each potential substring without having to redundantly check certain parts of the string.
This C solution utilizes the sliding window approach by evaluating each possible substring of the given word — resulting in an efficient determination of the longest valid substring, as outlined in the approach.
C++
Java
Python
C#
JavaScript
The time complexity of this implementation is O(n^2 * m) where n is the length of the word and m is the average length of the forbidden words. The space complexity is O(1).
Longest Valid Parentheses | Live Coding with Explanation | Leetcode - 32 • Algorithms Made Easy • 54,894 views views
Watch 9 more video solutions →Practice Length of the Longest Valid Substring with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor