无重复字符的最长子串（Longest Substring Without Repeating Characters）

无重复字符的最长子串

题目描述

https://leetcode.cn/problems/longest-substring-without-repeating-characters/

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

解题思路

核心观察

使用滑动窗口维护一个不包含重复字符的子串。窗口左边界为 l，右边界为 r（当前遍历到的字符）。

算法步骤

1. 使用集合 a 存储当前窗口中的字符
2. 右指针 r 不断向右扩展
3. 如果新字符 s[r] 已存在于窗口中，则收缩左边界 l，直到窗口中不再包含该字符
4. 更新最长子串长度 ans

代码实现

import sys

s = sys.stdin.readline().strip()

a = set()
l = 0
ans = 0
for r in range(len(s)):
    while s[r] in a:
        a.remove(s[l])
        l += 1
    a.add(s[r])
    ans = max(ans, r - l + 1)

print(ans)

代码解析

• a 集合：存储当前滑动窗口中的字符
• l：窗口左边界
• r：窗口右边界（遍历指针）
• 当遇到重复字符时，不断移除左边界字符直到窗口中不存在该字符

时间复杂度

• 每个字符最多被左、右指针访问一次：O(n)
• 集合操作平均 O(1)
• 总计：O(n)