连续子序列

题目分析

给定一个由 ASCII 字母和数字组成的字符串，找出其中不含重复字符的最长子串的长度。

思路

本题是经典的滑动窗口问题。

维护一个窗口 [left, right]，保证窗口内没有重复字符：

1. 用哈希表 last 记录每个字符最后一次出现的位置。
2. 右指针 right 从左到右遍历字符串，对于当前字符 s[right]：

- 如果该字符在窗口内出现过（即 last[ch] >= left），则将 left 跳到 last[ch] + 1，跳过重复字符。

- 更新 last[ch] = right。

- 更新答案 ans = max(ans, right - left + 1)。

1. 每个字符最多被左右指针各访问一次，因此总时间复杂度为线性。

代码

import sys
input = sys.stdin.readline

def solve():
    s = input().strip()
    last = {}
    ans = 0
    left = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        ans = max(ans, right - left + 1)
    print(ans)

solve()

复杂度分析

• 时间复杂度: ，其中 为字符串长度。左右指针各遍历一次字符串。
• 空间复杂度: ，其中 为字符集大小。哈希表最多存储字符集大小的键值对。