Length of the Longest Valid Substring — Problem & Solution
Length of the Longest Valid Substring solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Length of the Longest Valid Substring is a hard coding problem on arrays, strings and hash table, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Strings, Hash Table, Sliding Window
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A chat filter on CodeKairo blocks a list of forbidden strings. A string is valid if none of its substrings is in forbidden.
Given word and forbidden, return the length of the longest valid substring of word. The empty substring is valid, so the answer may be 0.
Example 1
Input: word = "kairokai", forbidden = ["ok","ai"]
Output: 3
Explanation: `iro` avoids both; any longer window contains `ai` or `ok`.
Example 2
Input: word = "codekairo", forbidden = ["z"]
Output: 9
Example 3
Input: word = "aaaa", forbidden = ["a"]
Output: 0
Constraints
1 <= word.length <= 10^5word consists only of lowercase English letters1 <= forbidden.length <= 10^51 <= forbidden[i].length <= 10forbidden[i] consists only of lowercase English letters
Hints for Length of the Longest Valid Substring
Hint 1
Validity is monotone: if a window is valid, every window inside it is valid. Think sliding window — for each right end, find the smallest valid left end.
Hint 2
When the right end moves to
r, the only new substrings are those ending atr, and a forbidden word has length at most 10, so only 10 of them can matter.Hint 3
Put
forbiddenin a hash set. Forifromrdown tomax(left, r - 9), ifword[i..r]is forbidden, movelefttoi + 1and stop. The window[left, r]is then the longest valid one ending atr.
How to solve Length of the Longest Valid Substring
Sweep the right end of a window. A newly appearing forbidden substring must end at the new right end and is at most 10 long, so each step needs at most 10 hash-set lookups to push the left end past every forbidden occurrence.
Approach
- Insert all forbidden strings into a hash set; set
left = 0,best = 0. - For each
rfrom 0 ton - 1: forifromrdown tomax(left, r - 9), ifword[i..r]is in the set, setleft = i + 1and break. - Update
best = max(best, r - left + 1). - Return
best.
Why it works
Invariant: [left, r] is the longest valid window ending at r. Moving to r + 1 can only introduce forbidden substrings that end at r + 1; scanning start positions from right to left finds the one with the largest start first, and the window must begin after it. Starts before left need not be checked because left already excludes an earlier forbidden occurrence. Valid windows are closed under shrinking, so the best window for each right end is the one starting at left.
Complexity
- Time —
O(n · 10 · 10) — at most 10 lookups of strings of length at most 10 per position - Space —
O(total length of forbidden)
Pitfalls
- Scanning
ifrom left to right stops at the wrong forbidden substring and leaves the window invalid. - Starting the scan below
leftis wasted work; starting belowr - 9is pointless because forbidden words are at most 10 long. - Checking every substring of
wordagainst every forbidden word is far too slow.
Reference solution
Python
from typing import List
def longestValidSubstring(word: str, forbidden: List[str]) -> int:
bad = set(forbidden)
left = 0
best = 0
for r in range(len(word)):
for i in range(r, max(left, r - 9) - 1, -1):
if word[i:r + 1] in bad:
left = i + 1
break
best = max(best, r - left + 1)
return bestJava
public static int longestValidSubstring(String word, String[] forbidden) {
Set<String> bad = new HashSet<>(Arrays.asList(forbidden));
int left = 0, best = 0;
for (int r = 0; r < word.length(); r++) {
for (int i = r; i >= Math.max(left, r - 9); i--) {
if (bad.contains(word.substring(i, r + 1))) {
left = i + 1;
break;
}
}
best = Math.max(best, r - left + 1);
}
return best;
}C++
int longestValidSubstring(string word, vector<string>& forbidden) {
unordered_set<string> bad(forbidden.begin(), forbidden.end());
int left = 0, best = 0, n = word.size();
for (int r = 0; r < n; r++) {
for (int i = r; i >= max(left, r - 9); i--) {
if (bad.count(word.substr(i, r - i + 1))) {
left = i + 1;
break;
}
}
best = max(best, r - left + 1);
}
return best;
}JavaScript
var longestValidSubstring = function(word, forbidden) {
var bad = new Set(forbidden);
var left = 0, best = 0;
for (var r = 0; r < word.length; r++) {
for (var i = r; i >= Math.max(left, r - 9); i--) {
if (bad.has(word.substring(i, r + 1))) {
left = i + 1;
break;
}
}
best = Math.max(best, r - left + 1);
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.