Problem
Find the longest substring that contains none of the forbidden strings. In this practice version all text is lowercase and every forbidden pattern has length at most L.
Worked examples
Input: text = "abcde", forbidden = ["bc"]
Output: 3
The substring "cde" is valid; any substring containing "bc" is not.
Hints
Hint 1
Maintain the earliest allowed start of a window.
Hint 2
At each ending position, inspect suffixes no longer than L.
Solution approach
- Keep forbidden patterns in a set and a left boundary initially zero.
- For each right boundary, examine suffixes ending there. If a forbidden suffix starts at k, move left to at least k + 1.
- Update the best length after enforcing every forbidden suffix. Python slicing costs O(L), so account for that in the bound.
Python reference implementation
def longest_allowed(text, forbidden):
bad = set(forbidden)
L = max(map(len, bad), default=0)
left = best = 0
for right in range(len(text)):
for size in range(1, min(L, right - left + 1) + 1):
start = right - size + 1
if text[start:right + 1] in bad:
left = max(left, start + 1)
best = max(best, right - left + 1)
return bestComplexity
O(n L²) time with Python substring copies; O(total pattern characters + L) extra space. A trie can reduce matching to O(n L).
Report & practice notes
The report includes mixed-case examples but unclear case-matching rules. This practice version explicitly uses lowercase input; confirm case sensitivity in an actual assessment.
Read the candidate’s source report ↗