最长无重复字符子串问题

题目描述：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。例如，输入 "abcabcbb"，输出应为 3，因为最长无重复字符子串是 "abc"。

解题过程：

1. 问题分析：我们需要在字符串中找到一段连续的子串，该子串内所有字符都是唯一的，且要求该子串的长度尽可能长。这是一个典型的滑动窗口问题。

2. 暴力解法思路：最直观的方法是枚举所有可能的子串，检查每个子串是否有重复字符。对于长度为 n 的字符串，子串总数为 O(n²)，检查每个子串需要 O(n) 时间，总时间复杂度为 O(n³)，效率太低，不可取。

3. 滑动窗口优化思路：使用两个指针（left 和 right）表示当前考察的子串边界。右指针 right 向右移动，扩大窗口；当遇到重复字符时，左指针 left 向右移动，缩小窗口。这样只需遍历一次字符串，时间复杂度可降为 O(n)。

4. 具体步骤：

   • 初始化 left = 0，max_len = 0，并使用一个哈希集合（或字典）记录当前窗口内出现的字符及其最新索引。
   • 遍历字符串，right 从 0 开始：
     • 若当前字符 s[right] 已在集合中，且其索引 ≥ left（在窗口内），说明出现重复，需要将 left 移动到该重复字符上次出现位置的下一个位置。
     • 更新当前字符在集合中的索引为 right。
     • 计算当前窗口长度（right - left + 1），并更新 max_len。
   • 返回 max_len。

5. 示例演示（以 "abcabcbb" 为例）：

   • left=0, right=0: 字符 'a'，加入集合，max_len=1。
   • right=1: 'b' 无重复，max_len=2。
   • right=2: 'c' 无重复，max_len=3。
   • right=3: 'a' 重复（上次索引0 ≥ left），left 移至 1，窗口变为 "bca"，max_len=3。
   • right=4: 'b' 重复（上次索引1 ≥ left），left 移至 2，窗口变为 "cab"，max_len=3。
   • 依此类推，最终 max_len=3。

6. 边界情况处理：

   • 空字符串：直接返回 0。
   • 全重复字符（如 "aaaa"）：max_len=1。
   • 无重复字符（如 "abc"）：max_len=3。

7. 代码实现（Python）：

def lengthOfLongestSubstring(s: str) -> int:
    char_index = {}  # 记录字符最近出现的位置
    left = 0
    max_len = 0
    for right, char in enumerate(s):
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1  # 移动左指针到重复字符的下一位
        char_index[char] = right  # 更新字符位置
        max_len = max(max_len, right - left + 1)
    return max_len

8. 复杂度分析：
   • 时间复杂度：O(n)，每个字符最多被访问两次（左右指针各一次）。
   • 空间复杂度：O(min(m, n))，其中 m 为字符集大小（如 ASCII 为 128），n 为字符串长度。

通过滑动窗口和哈希表的结合，我们高效地解决了最长无重复字符子串问题。