Skip to main content
Talentd

Length of the Longest Valid Substring - Solution & Explanation

HardArrayHash TableStringSliding Window9 min readAsked at: Amazon, Meta, Google
Practice this problem

Problem Statement

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 <= 105
  • word consists only of lowercase English letters.
  • 1 <= forbidden.length <= 105
  • 1 <= forbidden[i].length <= 10
  • forbidden[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.

This C solution utilizes the sliding window approach by evaluating each possible substring of the given word — resulting in an efficient determination of the longest valid substring, as outlined in the approach.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity of this implementation is O(n^2 * m) where n is the length of the word and m is the average length of the forbidden words. The space complexity is O(1).

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window Approach

The time complexity of this implementation is O(n^2 * m) where n is the length of the word and m is the average length of the forbidden words. The space complexity is O(1).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Substring EnumerationO(n^3)O(1)Conceptual baseline or very small input sizes
Sliding Window + Hash SetO(n * L) where L ≤ 10O(f)General optimal solution for interviews and competitive programming
Trie-Based Forbidden MatchingO(n * L)O(total forbidden characters)When many forbidden strings share prefixes or substring creation is expensive

Video Solution

2781. Length of the Longest Valid Substring (Leetcode Hard) • Programming Live with Larry • 3,900 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Length of the Longest Valid Substring with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays