重复字符追捕 · 安检门滑窗

怎样从“字符串 abcabcbb 是一条字符跑道——找出不含重复字符的最长连续子串长度。”推导出 滑动窗口 · 变长 · 安检门，并证明每次状态变化都不会漏掉答案？

中心结论：蓝色扫描框 [L,R] 维护连续无重复安全区；R 纳入新字符，若 oldIndex >= L 则 L 跳到 oldIndex+1；best 记录最长窗口。

在一个字符串中寻找没有重复字母的最长子串。

在本站主例中，字符串 abcabcbb 是一条字符跑道——找出不含重复字符的最长连续子串长度。

算法最终需要得到或观察：最长无重复子串长度 3，可以是 abc / bca / cab。

枚举所有子串会反复统计大量相同字符；窗口只处理右端新加入和左端刚移出的增量。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“伸缩窗口”，明确答案需要观察什么。
2. 2状态只维护 左闸门 L、右扫描 R、lastSeen 雷达、best 记录牌。
3. 3转移每一步按照 蓝色扫描框 [L,R] 维护连续无重复安全区；R 纳入新字符，若 oldIndex >= L 则 L 跳到 oldIndex+1；best 记录最长窗口。
4. 4收尾读取 最长无重复子串长度 3，可以是 abc / bca / cab。，并复核边界与复杂度。

右端扩张负责获得新信息，左端收缩负责恢复合法性。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：左闸门 L、右扫描 R、lastSeen 雷达、best 记录牌。

这一题和第 438 题，第 3 题，第 76 题，第 567 题类似，用的思想都是"滑动窗口"。

滑动窗口的右边界不断的右移，只要没有重复的字符，就持续向右扩大窗口边界。一旦出现了重复字符，就需要缩小左边界，直到重复的字符移出了左边界，然后继续移动滑动窗口的右边界。以此类推，每次移动需要计算当前长度，并判断是否需要更新最大长度，最终最大的值就是题目中的所求。

蓝色扫描框 [L,R] 维护连续无重复安全区；R 纳入新字符，若 oldIndex >= L 则 L 跳到 oldIndex+1；best 记录最长窗口。

执行过程中持续维护：左闸门 L、右扫描 R、lastSeen 雷达、best 记录牌。

正确性依赖以下不变量：窗口 [L, R] 内任意时刻都不含重复字符。

面试时可以压缩为：变长滑动窗口 + 哈希 last：右指针纳入字符，若 old 存在且 old >= left 则 left = old + 1；更新 last 与 best = max(best, right-left+1)。L 只向右，O(n)。

落到当前题，执行机制可以压缩为：蓝色扫描框 [L,R] 维护连续无重复安全区；R 纳入新字符，若 oldIndex >= L 则 L 跳到 oldIndex+1；best 记录最长窗口。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入字符串 abcabcbb 是一条字符跑道——找出不含重复字符的最长连续子串长度。 因为：蓝色扫描框 [L,R] 维护连续无重复安全区；R 纳入新字符，若 oldIndex >= L 则 L 跳到 oldIndex+1；best 记录最长窗口。
2. 2R=0 · 扫描机器人纳入 a右边界 R 从第一个字符开始探索。窗口里只有 a，没有重复，best 更新为 1。 因为：无冲突时只扩张 R 并更新 lastSeen / best。
3. 3R=2 · 纳入 c，窗口 abcc 也是新面孔。连续三字 abc 都合法，best 达到 3。 因为：无冲突时只扩张 R 并更新 lastSeen / best。
4. 4R=3 · 重复 a！L 闸门跳到 1又见到 a，雷达显示旧 a 在 0，且 0 >= L=0，说明旧 a 还在窗口内。L 必须跳到 1，窗口变成 bca。 因为：旧字符仍在窗口内时必须让 L 跳过它，否则窗口仍含重复。
5. 5R=4 · 旧 b 在 1，L 跳到 2b 的旧位置 1 仍 >= L=1，冲突成立。L 跳到 2，窗口变成 cab。 因为：旧字符仍在窗口内时必须让 L 跳过它，否则窗口仍含重复。
6. 6R=6 · 旧 b 在 4，L 跳到 5b 的旧位置 4 >= L=3，L 跳到 5，窗口缩短为 cb。 因为：旧字符仍在窗口内时必须让 L 跳过它，否则窗口仍含重复。
7. 7误区剧场 · abba演示 oldIndex < L 时为何不能让 L 回退。 因为：正确写法是 if (old >= left) left = old + 1，等价于 left = max(left, old+1)。
8. 8收尾与复杂度最长无重复子串长度 3，可以是 abc / bca / cab。 因为：时间 O(n) · 空间 O(min(n,Σ))。蓝色扫描框 [L,R] 维护连续无重复安全区；R 纳入新字符，若 oldIndex >= L 则 L 跳到 oldIndex+1；best 记录最长窗口。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// 解法一 位图
func lengthOfLongestSubstring(s string) int {
	if len(s) == 0 {
		return 0
	}
	var bitSet [256]bool
	result, left, right := 0, 0, 0
	for left < len(s) {
		// 右侧字符对应的 bitSet 被标记 true，说明此字符在 X 位置重复，需要左侧向前移动，直到将 X 标记为 false
		if bitSet[s[right]] {
			bitSet[s[left]] = false
			left++
		} else {
			bitSet[s[right]] = true
			right++
		}
		if result < right-left {
			result = right - left
		}
		if left+result >= len(s) || right >= len(s) {
			break
		}
	}
	return result
}

// 解法二 滑动窗口
func lengthOfLongestSubstring1(s string) int {
	if len(s) == 0 {
		return 0
	}
	var freq [127]int
	result, left, right := 0, 0, -1

	for left < len(s) {
		if right+1 < len(s) && freq[s[right+1]] == 0 {
			freq[s[right+1]]++
			right++

		} else {
			freq[s[left]]--
			left++
		}
		result = max(result, right-left+1)
	}
	return result
}

// 解法三 滑动窗口-哈希桶
func lengthOfLongestSubstring2(s string) int {
	right, left, res := 0, 0, 0
	indexes := make(map[byte]int, len(s))
	for left < len(s) {
		if idx, ok := indexes[s[left]]; ok && idx >= right {
			right = idx + 1
		}
		indexes[s[left]] = left
		left++
		res = max(res, left-right)
	}
	return res
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
    // 1. 主例
    //    输入：mode="longest-unique", text="abcabcbb"
    //    期望：最长无重复子串长度 3，可以是 abc / bca / cab。
    //
    // 2. 失败 / 未命中
    //    检查：L 只能向右不回退；abba 末位 a 时 oldIndex=0 < L=2，不能让 L 回到 1。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC209 长度最小的子数组；LC438 找所有字母异位词
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意字符串 abcabcbb 是一条字符跑道——找出不含重复字符的最长连续子串长度。
2. 2重复枚举所有子串会反复统计大量相同字符；窗口只处理右端新加入和左端刚移出的增量。
3. 3优化蓝色扫描框 [L,R] 维护连续无重复安全区；R 纳入新字符，若 oldIndex >= L 则 L 跳到 oldIndex+1；best 记录最长窗口。
4. 4证明窗口 [L, R] 内任意时刻都不含重复字符。
5. 5复杂度时间 O(n)，空间 O(min(n,Σ))