Length Of The Longest Valid Substring
01 · Problem
You are given a string word and an array of strings forbidden. A substring of word is valid if none of the strings in forbidden appears anywhere inside it as a substring.
Return the length of the longest valid substring of word. The empty substring is always valid, so the answer is 0 when every character of word is itself forbidden.
02 · Examples
word = "programmer", forbidden = ["mm","ro"]
5
"ro" sits at indices 1-2 and "mm" at 6-7. "ogram" (indices 2-6) avoids both and has length 5; stretching it either way would include a forbidden pair.
word = "bananas", forbidden = ["nan","s"]
4
"bana" (indices 0-3) is valid. Any substring reaching index 4 from before index 3 contains "nan", and anything ending at index 6 contains "s".
word = "abc", forbidden = ["d"]
3
The forbidden string never occurs, so the whole word is valid.
03 · Constraints
- 011 <= word.length <= 105
- 02word consists only of lowercase English letters
- 031 <= forbidden.length <= 105
- 041 <= forbidden[i].length <= 10
- 05forbidden[i] consists only of lowercase English letters
04 · Optimal complexity
- Time
- O(n * L^2)
- Space
- O(m * L)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.