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

题目链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/

代码

/**
 * 3. 无重复字符的最长子串
 * https://leetcode.cn/problems/longest-substring-without-repeating-characters/
 */

function lengthOfLongestSubstring(s: string): number {
    let left = 0; // 窗口左边界
    let res = 0; // 最长无重复子串长度
    const map = new Map<string, number>(); // 字符: 最后一次出现的位置
    for (let right = 0; right < s.length; right++) {
        // 之前出现过 并且在窗口内
        if (map.has(s[right]) && map.get(s[right])! >= left) {
            left = map.get(s[right])! + 1; // 移动左指针跳过该字符
        }
        map.set(s[right], right); // 更新字符出现位置
        res = Math.max(res, right - left + 1); // 当前窗口长度right - left + 1
    }
    return res;
}

思路

• 使用滑动窗口 + 哈希表（或 Map）记录每个字符上一次出现的位置。
• 右指针向右移动，遇到重复字符时，将左指针移动到该字符上次出现位置的下一位，以保证窗口内没有重复字符。
• 每次更新窗口长度的最大值。
• 时间复杂度 $O(n)$，空间复杂度 $O(1)$，其中 $n$ 为字符串长度，字符集大小有限。