LeetCode - 3.无重复字符的最长子串

题目描述

给定一个字符串 s，请找出其中不含有重复字符的最长子串长度。

这里需要注意的是「子串」必须连续，不能像「子序列」一样跳过字符。

思路

因为题目要求的是最长子串，所以我们需要维护一个连续区间，并在区间内出现重复字符时调整左边界。

一开始我理解错了：遇到重复字符时，以为要把前面的内容全部丢掉。实际上只需要把窗口左边界移动到「上一个重复字符」的下一个位置即可。

这正好对应滑动窗口的思路。常见写法有两种：

Set 写法：维护当前窗口内出现过的字符。遇到重复字符时，持续移动左指针，直到窗口内不再重复。
Map 写法：记录每个字符最近一次出现的位置。遇到重复字符时，直接把左指针跳到上次出现位置的后一位。

两种写法本质相同，区别在于 Set 更贴近窗口收缩的过程，Map 则利用下标记录让左指针一步跳到位。

实际处理

Set 写法

var lengthOfLongestSubstring = function(s) {
    let max = 0;
    const path = new Set();
    let left = 0;
    
    for (let right = 0; right < s.length; right++) {
        const char = s[right];
 
        while (path.has(char)) {
            path.delete(s[left]);
            left++;
        }
        
        path.add(char);
        max = Math.max(max, right - left + 1);
    }
 
    return max;
};

这段代码的关键是：当 s[right] 已经存在于窗口中时，说明当前窗口不合法，于是不断删除 s[left] 并右移 left，直到重复字符被移出窗口。

Map 写法

var lengthOfLongestSubstring = function(s) {
    let max = 0;
    const map = new Map();
    let left = 0;
 
    for (let right = 0; right < s.length; right++) {
        const char = s[right];
 
        if (map.has(char) && map.get(char) >= left) {
            left = map.get(char) + 1;
        }
 
        map.set(char, right);
 
        max = Math.max(max, right - left + 1);
    }
 
    return max;
};

Map 写法的重点是 map.get(char) >= left 这个判断。

如果某个字符虽然出现过，但它的位置已经在当前窗口左侧，就不能再影响当前窗口。只有当它上次出现的位置仍然在窗口内时，才需要更新 left。

例如字符串 abba：

扫到第二个 b 时，left 从 0 移到第一个 b 后面，也就是 2。
继续扫到最后一个 a 时，虽然 a 在下标 0 出现过，但此时 left 已经是 2，下标 0 不在当前窗口内，所以不能把 left 回退。

因此，left 只会向右移动，不会回退。