Length of the Longest Valid Substring solution and explanation
Google
9 more videos on this problem
2781. Length of the Longest Valid Substring (Leetcode Hard)Programming Live with Larry · 14:31 · 3K views
Leetcode Weekly contest 354 - Hard - Length of the Longest Valid SubstringPrakhar Agrawal · 19:54 · 3K views
Leetcode 2781. Length of the Longest Valid Substring (sliding window)LetsCode · 13:20 · 2K views
Length of the Longest Valid Substring | Leetcode 2781 | Sliding Window | C++Tech Courses · 16:23 · 2K views
Leetcode 2781 Length of the Longest Valid SubstringNail the Tech Interview · 22:17 · 1K views
Harder Follow-ups | 2781. Length of the Longest Valid Substring | Leetcode Weekly 354codingMohan · 33:53 · 1K views
Python Optimization 5X Speed Improvement - LeetCode 2781 Length of the Longest Valid SubstringvanAmsen · 7:23 · 848 views
Length of the Longest valid substring - Leetcode 2781Algorhythm · 15:38 · 357 views
2781. Length of the Longest Valid Substring | Leetcode Hard | Dynamic Programmingquebeat · 13:53 · 350 views
LeetCode 2781 Length of the Longest Valid SubstringHow we live in Texas · 5:31 · 207 views
The problem
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 <= 105wordconsists only of lowercase English letters.1 <= forbidden.length <= 1051 <= forbidden[i].length <= 10forbidden[i]consists only of lowercase English letters.
Approach overview
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.
Approach 1: Sliding Window Approach
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.
def longest_valid_substring(word, forbidden):
max_length = 0
n = len(word)
for i in range(n):
for j in range(i, n):
substr = word[i:j + 1]
if not any(f in substr for f in forbidden):
max_length = max(max_length, j - i + 1)
return max_length
word = "cbaaaabc"
forbidden = ["aaa", "cb"]
print(longest_valid_substring(word, forbidden))import java.util.List;
public class LongestValidSubstring {
public static void main(String[] args) {
String word = "cbaaaabc";
List<String> forbidden = List.of("aaa", "cb");
System.out.println(longestValidSubstring(word, forbidden));
}
public static int longestValidSubstring(String word, List<String> forbidden) {
int maxLength = 0;
for (int i = 0; i < word.length(); i++) {
for (int j = i; j < word.length(); j++) {
String sub = word.substring(i, j + 1);
if (!containsForbidden(sub, forbidden)) {
maxLength = Math.max(maxLength, sub.length());
}
}
}
return maxLength;
}
private static boolean containsForbidden(String s, List<String> forbidden) {
for (String f : forbidden) {
if (s.contains(f)) {
return true;
}
}
return false;
}
}#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
bool isForbidden(const string &substring, const vector<string> &forbidden) {
return any_of(forbidden.begin(), forbidden.end(), [&](const string &f) {
return substring.find(f) != string::npos;
});
}
int longestValidSubstring(const string &word, const vector<string> &forbidden) {
int maxLength = 0;
for (size_t i = 0; i < word.size(); ++i) {
for (size_t j = i; j < word.size(); ++j) {
string substring = word.substr(i, j - i + 1);
if (!isForbidden(substring, forbidden)) {
maxLength = max(maxLength, static_cast<int>(substring.size()));
}
}
}
return maxLength;
}
int main() {
vector<string> forbidden = {"aaa", "cb"};
string word = "cbaaaabc";
cout << longestValidSubstring(word, forbidden) << endl;
return 0;
}function longestValidSubstring(word, forbidden) {
let maxLength = 0;
for (let i = 0; i < word.length; i++) {
for (let j = i; j < word.length; j++) {
let substring = word.substring(i, j + 1);
if (!forbidden.some(f => substring.includes(f))) {
maxLength = Math.max(maxLength, j - i + 1);
}
}
}
return maxLength;
}
const word = "cbaaaabc";
const forbidden = ["aaa", "cb"];
console.log(longestValidSubstring(word, forbidden));#include <stdio.h>
#include <string.h>
#include <stdbool.h>
bool containsForbiddenSubstring(const char *s, char forbidden[][11], int forbiddenSize) {
for (int i = 0; i < forbiddenSize; ++i) {
if (strstr(s, forbidden[i])) {
return true;
}
}
return false;
}
int longestValidSubstring(const char *word, char forbidden[][11], int forbiddenSize) {
int maxLength = 0;
int n = strlen(word);
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
char temp[j - i + 2];
strncpy(temp, &word[i], j - i + 1);
temp[j - i + 1] = '\0';
if (!containsForbiddenSubstring(temp, forbidden, forbiddenSize)) {
int length = j - i + 1;
if (length > maxLength) {
maxLength = length;
}
}
}
}
return maxLength;
}
int main() {
char word[] = "cbaaaabc";
char forbidden[][11] = {"aaa", "cb"};
int forbiddenSize = 2;
printf("%d\n", longestValidSubstring(word, forbidden, forbiddenSize));
return 0;
}using System;
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
string word = "cbaaaabc";
List<string> forbidden = new List<string> { "aaa", "cb" };
Console.WriteLine(LongestValidSubstring(word, forbidden));
}
public static int LongestValidSubstring(string word, List<string> forbidden)
{
int maxLength = 0;
for (int i = 0; i < word.Length; i++)
{
for (int j = i; j < word.Length; j++)
{
string substring = word.Substring(i, j - i + 1);
if (!ContainsForbidden(substring, forbidden))
{
maxLength = Math.Max(maxLength, substring.Length);
}
}
}
return maxLength;
}
public static bool ContainsForbidden(string s, List<string> forbidden)
{
foreach (var f in forbidden)
{
if (s.Contains(f)) return true;
}
return false;
}
}In Python, this implementation leverages simple loops along with Python's substring finding capabilities to establish the longest substring without forbidden words.
The time complexity is O(n^2 * m) where n is the length of the input word, and m is the length of the forbidden array. The space complexity is O(1).
Approach 2: Default Approach
function longestValidSubstring(word: string, forbidden: string[]): number {
const s: Set<string> = new Set(forbidden);
const n = word.length;
let ans = 0;
for (let i = 0, j = 0; j < n; ++j) {
for (let k = j; k > Math.max(j - 10, i - 1); --k) {
if (s.has(word.substring(k, j + 1))) {
i = k + 1;
break;
}
}
ans = Math.max(ans, j - i + 1);
}
return ans;
}func longestValidSubstring(word string, forbidden []string) (ans int) {
s := map[string]bool{}
for _, x := range forbidden {
s[x] = true
}
n := len(word)
for i, j := 0, 0; j < n; j++ {
for k := j; k > max(j-10, i-1); k-- {
if s[word[k:j+1]] {
i = k + 1
break
}
}
ans = max(ans, j-i+1)
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window Approach | The time complexity is O(n^2 * m) where n is the length of the input word, and m is the length of the forbidden array. The space complexity is O(1). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Enumeration | O(n^3) | O(1) | Conceptual baseline or very small input sizes |
| Sliding Window + Hash Set | O(n * L) where L ≤ 10 | O(f) | General optimal solution for interviews and competitive programming |
| Trie-Based Forbidden Matching | O(n * L) | O(total forbidden characters) | When many forbidden strings share prefixes or substring creation is expensive |
Frequently asked questions
Is Length of the Longest Valid Substring easy or hard?
LeetCode classifies this problem as Hard because it combines sliding window logic with substring constraint handling. The key insight is limiting checks to the maximum forbidden length, which reduces a naive cubic approach to near linear time.
Length of the Longest Valid Substring Python/Java solution
Most implementations follow the same sliding window logic across languages. Python typically uses a set for forbidden strings and substring slicing for checks. Java and C++ implementations often rely on HashSet or unordered_set and iterate backward up to length 10 to validate substrings.
How to solve Length of the Longest Valid Substring in O(n)?
Use a sliding window and store forbidden patterns in a hash set. As you move the right pointer, check at most the last 10 characters ending at that index. If a forbidden substring is found, move the left pointer just after the start of that substring. This guarantees the window always stays valid while maintaining linear traversal.
What is the best approach for Length of the Longest Valid Substring?
The sliding window with a hash set of forbidden strings is the best approach. Move a right pointer across the string and check substrings ending at that position with maximum length 10. When a forbidden substring appears, shift the left boundary to exclude it. This runs in O(n * 10) time, effectively O(n).
Is Length of the Longest Valid Substring asked at Google/Amazon/Meta?
Problems combining sliding window and string pattern constraints frequently appear in interviews at companies like Amazon, Google, and Meta. Variants involving forbidden substrings, longest valid windows, or substring restrictions are common in mid to senior level coding rounds.
What data structure is used in Length of the Longest Valid Substring?
The primary data structures are a hash set for constant-time lookup of forbidden strings and two pointers for the sliding window. Some implementations also use a trie to efficiently match forbidden patterns while scanning the string.
What is the time complexity of Length of the Longest Valid Substring?
The optimal solution runs in O(n * L) time where L is the maximum length of a forbidden string. In this problem L is at most 10, so the runtime is effectively O(n). Space complexity is O(f) to store the forbidden strings in a hash set.