千问 LeetCode 2781. 最长合法子字符串的长度 JavaScript实现

这是 LeetCode 2781 题“最长合法子字符串的长度”的 JavaScript 版本实现。思路和 Java 版完全一致，依然采用双指针（滑动窗口）+ 逆向枚举的方法。

JavaScript 代码实现

/**
* @param {string} word
* @param {string[]} forbidden
* @return {number}
*/
var longestValidSubstring = function(word, forbidden) {
// 将 forbidden 数组存入 Set，实现 O(1) 时间复杂度的查找
const set = new Set(forbidden);

const n = word.length;
let ans = 0;
let left = 0;

// right 指针不断向右扩展
for (let right = 0; right < n; right++) {
// 从当前 right 位置开始，倒着往前最多检查 10 个字符
// 因为 forbidden 中最长的字符串长度只有 10
for (let i = right; i >= left && i > right - 10; i--) {
// 截取子串 word[i...right]
const sub = word.substring(i, right + 1);
if (set.has(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)。我们需要一个哈希集合（Set）来存储 forbidden 数组中的字符串，其中 M 是 forbidden 数组中所有字符串的总长度。