无重复字符的最长子串

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

子字符串 是字符串中连续的 非空 字符序列。

示例 1:

输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2:

输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3:

输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

简单做法： 遍历字符串，将不重复的每个字符放到Set中，Set中若存在该字符子串记录结束，记录最大长度，重新开始记录。

进阶做法：为了找到字符串中不含有重复字符的最长子串长度，可以使用滑动窗口结合哈希表的方法。该方法通过动态调整窗口的左右边界，并记录每个字符的最新位置，确保窗口内的字符始终唯一。

function lengthOfLongestSubstring(s) {
    const charMap = new Map();
    let left = 0;
    let maxLength = 0;

    for (let right = 0; right < s.length; right++) {
        const currentChar = s[right];
        // 如果字符已存在且在窗口内，调整左边界
        if (charMap.has(currentChar) && charMap.get(currentChar) >= left) {
            left = charMap.get(currentChar) + 1;
        }
        // 更新字符的最新位置
        charMap.set(currentChar, right);
        // 计算当前窗口长度并更新最大值
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

代码解释：

1. 哈希表记录字符位置：使用Map存储每个字符及其最新出现的索引。
2. 滑动窗口：维护左右指针left和right，确保窗口内的字符不重复。
3. 调整左边界：当遇到重复字符时，将左指针移动到该字符上一次出现位置的右侧。
4. 更新最大长度：在每次遍历时，计算当前窗口长度并更新最大值。

复杂度分析：

• 时间复杂度：O(n)，每个字符仅被访问一次。
• 空间复杂度：O(min(n, m))，其中m为字符集大小（如ASCII字符集为128）。

这种方法通过滑动窗口和哈希表的结合，高效地解决了子串问题，并确保了线性时间复杂度。