HardNo. 2781
Length of the Longest Valid Substring — LeetCode 2781 Python Solution
- Pattern
- Sliding Window
- Topics
- Array, Hash Table, String, Sliding Window
- Reading time
- 2 min
- Source
- leetcode.com
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.
Example
- 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.
Python solution
class Solution:
def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
s = set(forbidden)
ans = i = 0
for j in range(len(word)):
for k in range(j, max(j - 10, i - 1), -1):
if word[k : j + 1] in s:
i = k + 1
break
ans = max(ans, j - i + 1)
return ansComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Sliding Window
Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2781. Length of the Longest Valid Substring is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.
The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0003 | Longest Substring Without Repeating Characters | Medium |
| 0030 | Substring with Concatenation of All Words | Hard |
| 0049 | Group Anagrams | Medium |
| 0076 | Minimum Window Substring | Hard |
| 0139 | Word Break | Medium |
| 0140 | Word Break II | Hard |
Frequently asked questions
- How hard is LeetCode 2781. Length of the Longest Valid Substring?
LeetCode 2781. Length of the Longest Valid Substring is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2781. Length of the Longest Valid Substring?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2781. Length of the Longest Valid Substring?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2781. Length of the Longest Valid Substring cover?
LeetCode 2781. Length of the Longest Valid Substring is tagged Array, Hash Table, String and Sliding Window on LeetCode.