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.

Description Solution Video 14:31

2781. Length of the Longest Valid Substring

Hard38.3% acceptance3 companies

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

Asked at 3 companies

Amazon

Google Meta

Topics

14:31

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"cbaaaabc"
["aaa","cb"]

Input

"leetcode"
["de","le","e"]

Your code is saved on this device.Solution