千问 LeetCode 2781. 最长合法子字符串的长度 Java实现
这道题是 LeetCode 第 2781 题“最长合法子字符串的长度”，属于一道经典的双指针（滑动窗口）问题。
题目解析
给定一个字符串 word 和一个禁用字符串数组 forbidden，要求找出 word 中最长的子字符串，且该子字符串不包含 forbidden 中的任何一个字符串。
核心思路：双指针（滑动窗口） + 逆向枚举
1. 双指针维护合法区间：使用 left 和 right 两个指针维护一个合法的滑动窗口，right 不断向右扩展，left 在遇到非法情况时向右收缩。
2. 利用题目约束进行优化：题目中有一个非常关键的提示——forbidden[i] 的长度不超过 10。这意味着，当我们把 right 指针向右移动一位时，新产生的非法子串（如果存在）一定是以当前 right 为结尾，且长度在 1 到 10 之间的某个子串。
3. 逆向检查与更新左边界：每当 right 移动后，我们只需要从 right 开始，倒着往前最多枚举 10 个字符（即检查 word.substring(i, right + 1) 是否在禁用列表中）。如果发现某个子串在 forbidden 中，说明当前的 left 必须收缩到这个非法子串的右边（即 left = i + 1），从而保证窗口 [left, right] 始终是合法的。
Java 代码实现
import java.util.HashSet;
import java.util.List;
import java.util.Set;
class Solution {
public int longestValidSubstring(String word, List<String> forbidden) {
// 将 forbidden 数组存入 HashSet，实现 O(1) 时间复杂度的查找
Set<String> set = new HashSet<>(forbidden);
int n = word.length();
int ans = 0;
int left = 0;
// right 指针不断向右扩展
for (int right = 0; right < n; right++) {
// 从当前 right 位置开始，倒着往前最多检查 10 个字符
// 因为 forbidden 中最长的字符串长度只有 10
for (int i = right; i >= left && i > right - 10; i--) {
// 截取子串 word[i...right]
String sub = word.substring(i, right + 1);
if (set.contains(sub)) {
// 如果发现了非法子串，左指针必须收缩到该非法子串的右侧
left = i + 1;
// 找到一个非法的就可以停止了，因为我们要找的是最靠左的冲突点来更新 left
break;
}
}
// 更新最长合法子字符串的长度
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
复杂度分析
* 时间复杂度：O(N)。虽然代码中有一个嵌套的 for 循环，但由于 forbidden 字符串的最大长度限制为 10，内层循环最多只会执行 10 次（常数级别）。因此，整体时间复杂度取决于外层 right 指针的遍历，即 O(N)，其中 N 是 word 的长度。
* 空间复杂度：O(M)。我们需要一个哈希集合来存储 forbidden 数组中的字符串，其中 M 是 forbidden 数组中所有字符串的总长度。
这种方法巧妙地利用了数据范围的限制，将原本可能需要复杂字符串匹配（如 AC自动机/Trie图）的问题，简化为了非常直观且高效的双指针滑动窗口问题。