最长无重复字符子串

题目

最长无重复字符子串

信息

• 类型：问答
• 难度：⭐⭐

考点

滑动窗口,哈希表,字符串处理

快速回答

使用滑动窗口和哈希表记录字符索引：

• 初始化左指针和最大长度变量
• 右指针遍历字符串，用哈希表记录字符最新位置
• 当遇到重复字符时，移动左指针到重复字符的下一个位置
• 每次迭代更新最大长度：max_len = max(max_len, right - left + 1)

时间复杂度：O(n)，空间复杂度：O(字符集大小)

解析

问题描述

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

• 输入 "abcabcbb" → 输出 3（"abc"）
• 输入 "bbbbb" → 输出 1（"b"）
• 输入 "pwwkew" → 输出 3（"wke"）

核心原理：滑动窗口

滑动窗口是处理子串/子数组问题的经典技巧：

1. 用左右指针定义窗口边界（left, right）
2. 右指针主动向右扫描扩展窗口
3. 当遇到重复字符时，左指针被动向右收缩窗口
4. 哈希表记录字符最后出现的位置（字符 → 索引映射）

代码实现（Python）

def lengthOfLongestSubstring(s: str) -> int:
    char_index = {}  # 存储字符最后出现的索引
    left = 0         # 窗口左边界
    max_len = 0      # 最大长度

    for right in range(len(s)):
        # 如果字符在窗口中已存在
        if s[right] in char_index and char_index[s[right]] >= left:
            # 移动左边界到重复字符的下一个位置
            left = char_index[s[right]] + 1

        # 更新字符的最新位置
        char_index[s[right]] = right

        # 更新最大长度
        max_len = max(max_len, right - left + 1)

    return max_len

最佳实践

• 哈希表优化：使用字典实现O(1)时间复杂度的字符查找
• 边界检查：确保char_index[s[right]] >= left，避免处理历史重复字符
• 空间优化：如果字符集固定（如ASCII），可用128/256大小的数组替代哈希表

常见错误

扩展知识

• 变种问题：
  • 最长无重复字符子串（本题）
  • 最小覆盖子串（LeetCode 76）
  • 至多包含K个不同字符的最长子串（LeetCode 340）
• 算法选择：
  • 当字符集较小时：数组比哈希表更高效
  • 当字符串很长时：滑动窗口优于动态规划
• 复杂度对比：

  方法	时间复杂度	空间复杂度
  暴力枚举	O(n³)	O(1)
  动态规划	O(n²)	O(n)
  滑动窗口	O(n)	O(m) m为字符集大小