本文深入探讨了求解字符串中最长无重复子串长度的经典问题，并重点分析了使用滑动窗口算法的实现。文章首先分析了常见解法的时间复杂度，并提供了一个高效且易于理解的 JavaScript 实现，结合示例代码和详细注释，帮助读者掌握滑动窗口算法的精髓，并能灵活应用于解决类似字符串处理问题。
滑动窗口算法：O(n) 时间复杂度的解决方案
经典的“最长无重复子串”问题，要求在一个字符串中找到最长的子串，该子串中不包含重复字符。一种高效的解决方案是使用滑动窗口算法，该算法可以在 O(n) 的时间复杂度内解决此问题，其中 n 是字符串的长度。
算法思路
滑动窗口算法的核心思想是维护一个窗口，该窗口在字符串上滑动，并在滑动过程中动态调整窗口的大小，以满足问题的约束条件（在本例中，约束条件是窗口内的字符不能重复）。
具体步骤如下：
初始化： 定义两个指针 start 和 end，分别指向窗口的起始位置和结束位置。初始时，start 和 end 都指向字符串的第一个字符。同时，使用一个 Map 数据结构（或其他合适的哈希表）来记录窗口内每个字符的最新位置。
滑动窗口： end 指针不断向右移动，将新的字符加入窗口。
-
检查重复： 每当 end 指针指向一个新的字符时，检查该字符是否已经在窗口中出现过（即，是否在 Map 中存在）。
- 如果字符未出现过： 将该字符及其位置加入 Map，并更新最长无重复子串的长度。
- 如果字符已经出现过： 说明当前窗口内出现了重复字符，需要调整窗口的起始位置 start。将 start 指针移动到重复字符上次出现的位置之后（即 Map.get(str[end])）。同时，更新 start 指针时，需要确保 start 指针不会倒退，因此需要使用 Math.max(map.get(str[end]), start) 来确保 start 指针始终保持在当前位置或更靠右的位置。
更新最长长度： 在每次滑动窗口后，都需要更新最长无重复子串的长度。
循环： 重复步骤 2-4，直到 end 指针到达字符串的末尾。
JavaScript 代码示例
const lengthOfLongestSubstring = str => {
let cnt = 0;
let n = str.length;
let answer = 0;
let map = new Map(); // to store the strings and their length
for (let start = 0, end = 0; end < n; end++) { // slide
// move start if the character is already in the map
if (map.has(str[end])) start = Math.max(map.get(str[end]), start);
answer = Math.max(answer, end - start + 1); // longest string
map.set(str[end], end + 1);
cnt++
}
return answer;
}
// 示例测试
["abcabcbb", "bbbbb", "pwwkew", "abcdefghabcdefgh"].forEach(str => console.log(str + ": " + lengthOfLongestSubstring(str)))代码解释：
- map: 使用 Map 数据结构来存储字符及其在字符串中的索引。
- start 和 end: start 指针指向当前窗口的起始位置，end 指针指向当前窗口的结束位置。
- if (map.has(str[end])) start = Math.max(map.get(str[end]), start);: 如果当前字符 str[end] 已经在 map 中存在，则将 start 指针移动到 map.get(str[end]) 的位置，确保窗口内没有重复字符。使用 Math.max 避免 start 指针倒退。
- answer = Math.max(answer, end - start + 1);: 更新最长无重复子串的长度。
- map.set(str[end], end + 1);: 将当前字符 str[end] 及其索引 end + 1 存入 map 中。
时间和空间复杂度
- 时间复杂度： O(n)，因为 start 和 end 指针最多遍历字符串一次。
- 空间复杂度： O(min(m, n))，其中 m 是字符集的大小，n 是字符串的长度。空间复杂度取决于 Map 中存储的字符数量，最坏情况下，Map 需要存储整个字符串中的所有字符。
总结与注意事项
滑动窗口算法是一种解决字符串问题的有效方法，特别是在需要寻找满足特定约束条件的子串时。 理解滑动窗口的原理，并能够灵活运用，可以帮助我们解决许多类似的字符串处理问题。
注意事项：
- 在实现滑动窗口算法时，需要仔细考虑窗口的起始位置和结束位置的更新逻辑，确保窗口始终满足问题的约束条件。
- 根据具体问题的特点，选择合适的数据结构来存储窗口内的信息，例如 Map、Set 或数组。
- 注意处理边界情况，例如空字符串或字符串长度为 1 的情况。
通过本文的学习，相信你已经掌握了使用滑动窗口算法解决“最长无重复子串”问题的精髓。希望你能将这种思想应用到其他字符串处理问题中，并不断提升自己的编程能力。
