Length of the Longest Valid Substring - Video Solutions

Problem Overview: You get a string word and a list of forbidden strings. The task is to find the maximum length substring of word that does not contain any forbidden string as a substring.

Approach 1: Brute Force Substring Check (O(n^3) time, O(1) space)

The straightforward idea is to generate every possible substring of word using two nested loops. For each substring, check whether any forbidden word appears inside it. This requires scanning the substring or checking each forbidden pattern individually. Since there are O(n^2) substrings and each validation may take O(n) time, the worst-case complexity becomes O(n^3). This approach works only for very small inputs and mainly helps you reason about the problem before optimizing.

Approach 2: Sliding Window with Hash Set (O(n * L) time, O(f) space)

The optimized strategy uses a sliding window over the string. Store all forbidden words in a hash table for O(1) lookups. As you expand the right pointer of the window, check substrings that end at the current position. A key constraint makes this efficient: every forbidden string has length ≤ 10. That means you only need to check at most the last 10 characters ending at the current index.

For each index right, iterate backward up to 10 characters and form substrings word[right-k:right+1]. If any substring exists in the forbidden set, move the left boundary to right - k + 1. This ensures the current window never includes a forbidden pattern. Update the answer using right - left + 1. Each index performs at most 10 checks, so the total runtime becomes O(n * 10), effectively O(n).

Approach 3: Trie-Based Forbidden Matching (O(n * L) time, O(total forbidden chars) space)

Another approach builds a trie from all forbidden strings. Instead of hashing substrings, you traverse the trie while scanning characters backward from the current index. If a trie path reaches a terminal node, you detected a forbidden substring and adjust the left boundary. This technique avoids repeated substring creation and can be slightly faster in languages where substring operations are expensive. It also scales well if forbidden patterns share prefixes.

The problem combines string scanning with boundary control, making it a classic use case for string processing plus sliding window logic. The main trick is recognizing the maximum forbidden length and limiting checks to that range.

Recommended for interviews: The sliding window with hash set approach. It demonstrates awareness of substring constraints, efficient window management, and constant-time lookups. Mentioning the brute force approach first shows baseline reasoning, but implementing the optimized O(n) window solution is what interviewers typically expect.