Amazon Sliding Window：最长无重复子串，左边界为何不能倒退？

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练返回最长连续子串长度，字符单位Python Unicode code point；空串0。
• 不按字节计数，也不按可见字形cluster；大小写区分。

解题路线

1. 维护last[ch]和left。看到当前ch时left=max(left,last[ch]+1)，再更新last到right，窗口[right-left+1]更新答案。
2. left不能倒退：last[ch]可能在当前窗口左侧，若直接赋last+1会把已排除的重复重新纳入。max保证只在本窗口发生重复时前移。
3. 不变量：窗口内字符各一次，left最靠左且满足无重复。每个右端点取这个最长合法后缀，枚举全部右端点便获得全局最大。
4. 如果要输出子串，记录最佳起点和长度即可；切片只在最终构造，别每次构造窗口字符串导致二次复杂度。输入normalize后索引映射需另定。

手动走一遍

训练abba：处理第二b将left推到2，末尾a的旧last=0不能把left退回1，否则会错认为bba合法。正确最长2；abcabcbb最长3。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def longest_unique_length(text):
    """Unicode code points; contiguous substring, not subsequence."""
    last={}
    left=answer=0
    for right,ch in enumerate(text):
        left=max(left,last.get(ch,-1)+1)
        last[ch]=right
        answer=max(answer,right-left+1)
    return answer

复杂度

O(n)期望时间、O(u)最后位置空间，固定字母表可用数组。输出子串额外O(answer_length)构造。

易错点与追问

容易失分的边界

• left直接last+1导致倒退。
• 把最长不重复子序列当子串。
• 每次set整个窗口导致O(n²)。

继续深挖

• 允许最多K个不同字符怎样改？
• 可见字形计数需要什么预处理？
• 流式返回最佳文本要保留哪些状态？