What is the optimal approach for solving Length of the Longest Valid Substring?

The optimal approach involves using a sliding window to keep track of the current valid substring and hash tables to quickly check forbidden substrings.

How can hash tables be used in the Length of the Longest Valid Substring problem?

Hash tables allow for constant-time lookup to determine if a substring exists in the forbidden list, speeding up the validation process.

Why is the sliding window technique important in this problem?

The sliding window technique ensures we only scan relevant substrings, reducing unnecessary checks and improving performance.

How does GhostInterview assist with solving this problem?

GhostInterview provides step-by-step problem-solving guidance and suggests optimal algorithms like sliding windows and hash lookups to solve this problem efficiently.

What should I avoid when solving the Length of the Longest Valid Substring?

Avoid using a brute-force approach to generate all possible substrings, as this will lead to time inefficiencies for large inputs.

#2781

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

最长合法子字符串的长度

给你一个字符串 word 和一个字符串数组 forbidden 。如果一个字符串不包含 forbidden 中的任何字符串，我们称这个字符串是合法的。请你返回字符串 word 的一个最长合法子字符串的长度。子字符串指的是一个字符串中一段连续的字符，它可以为空。示例 1：输入： w…

数组哈希表字符串滑动窗口

题目描述

给你一个字符串 word 和一个字符串数组 forbidden 。

如果一个字符串不包含 forbidden 中的任何字符串，我们称这个字符串是合法的。

请你返回字符串 word 的一个 最长合法子字符串 的长度。

子字符串 指的是一个字符串中一段连续的字符，它可以为空。

示例 1：

输入：word = "cbaaaabc", forbidden = ["aaa","cb"]
输出：4
解释：总共有 11 个合法子字符串："c", "b", "a", "ba", "aa", "bc", "baa", "aab", "ab", "abc" 和 "aabc"。最长合法子字符串的长度为 4 。
其他子字符串都要么包含 "aaa" ，要么包含 "cb" 。

示例 2：

输入：word = "leetcode", forbidden = ["de","le","e"]
输出：4
解释：总共有 11 个合法子字符串："l" ，"t" ，"c" ，"o" ，"d" ，"tc" ，"co" ，"od" ，"tco" ，"cod" 和 "tcod" 。最长合法子字符串的长度为 4 。
所有其他子字符串都至少包含 "de" ，"le" 和 "e" 之一。

提示：

1 <= word.length <= 10⁵
word 只包含小写英文字母。
1 <= forbidden.length <= 10⁵
1 <= forbidden[i].length <= 10
forbidden[i] 只包含小写英文字母。

lightbulb

解题思路

方法一：哈希表 + 双指针

我们用哈希表 $s$ 记录所有禁止的字符串，然后用双指针 $i$ 和 $j$ 遍历字符串 $word$ ，其中 $i$ 和 $j$ 分别表示当前合法子字符串的左右边界。

接下来，我们枚举子字符串的右端点 $j$ ，判断此时 $word[k..j]$ 是否合法，如果不合法，那么我们更新 $i = k + 1$ 。接下来更新答案 $ans = \max(ans, j - i + 1)$ 。

时间复杂度 $O(n \times \max(|forbidden[i]|^2) + m)$ ，空间复杂度 $O(m)$ 。其中 $n$ 和 $m$ 分别表示字符串 $word$ 和 $forbidden$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

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 ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates a clear understanding of array scanning and sliding window techniques.
question_mark
Candidate effectively applies hash tables to optimize substring validation.
question_mark
Candidate is able to balance correctness and efficiency in their solution approach.

warning

常见陷阱

外企场景

error
Incorrect window shrinking when a forbidden substring is found, leading to missed valid substrings.
error
Overlooking the need for efficient substring validation, leading to poor performance for large inputs.
error
Improper handling of the case when there are no valid substrings, which can lead to incorrect results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handle cases where the forbidden list is very large and requires additional optimizations.
arrow_right_alt
Extend the problem to handle uppercase characters or other alphabet types.
arrow_right_alt
Consider cases where all substrings are forbidden and the output should be zero.

help

常见问题

外企场景

继续练习

#2799 统计完全子数组的数目 #2747 统计没有收到请求的服务器数目 #2744 最大字符串配对数目