这道题是 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, ListString forbidden) {// 将 forbidden 数组存入 HashSet实现 O(1) 时间复杂度的查找SetString 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 中最长的字符串长度只有 10for (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;// 找到一个非法的就可以停止了因为我们要找的是最靠左的冲突点来更新 leftbreak;}}// 更新最长合法子字符串的长度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图的问题简化为了非常直观且高效的双指针滑动窗口问题。
