企业官网建设流程全解析

• 教程
• 文档
• 知识库

本篇基于「算法通关手册」AlgoNote 仓库中 0159. 至多包含两个不同字符的最长子串题解 展开，系统讲解使用「滑动窗口 + 哈希表」在字符串上求「最多包含两种字符的最长连续子串」的完整思路、逐行代码与复杂度分析，并延伸对比仓库中 0340. 至多包含 K 个不同字符的最长子串、0003. 无重复字符的最长子串 等同类滑动窗口问题，帮助你掌握一类「不同字符/元素种类数受限」的区间问题通用解法。

1. 题目信息

• 题目编号：0159（LeetCode 159，Premium 会员题）
• 标签：哈希表、字符串、滑动窗口
• 难度：中等
• 题目链接：原题解文档中给出的题目链接为https://leetcode.cn/problems/longest-substring-with-at-most-two-distinct-characters/，题目编号在仓库 0100-0199 题解索引 中有收录。

2. 题目大意

给定一个字符串s，要求找出至多包含两个不同字符的最长子串t，并返回该子串的长度。

理解要点：

• 「两个不同字符」是指子串内出现的字符种类数最多为 2，例如"aabbc"中的子串"aabb"（含a、b两种字符）合法，而"abbc"（含a、b、c三种字符）不合法；
• 子串必须是连续的，不能跳过字符；
• 返回的是满足条件的最长子串的长度，而非子串本身。

3. 解题思路：滑动窗口 + 哈希表

3.1 为什么用滑动窗口

对于「求满足某条件的连续子区间的最长/最短长度」类问题，滑动窗口是经典解法。仓库基础篇 滑动窗口算法 中给出定义：

滑动窗口算法（Sliding Window）：在数组 / 字符串上维护一个固定或可变长度的窗口，通过滑动和缩放窗口，动态维护区间内的最优解。

本题属于不定长度（可变长度）滑动窗口：窗口大小不固定，需要在滑动过程中动态调整左右边界，维护「窗口内字符种类数不超过 2」这一约束，同时记录窗口的最大长度。滑动窗口通过动态调整左右边界避免重复遍历，能将暴力枚举所有子串的 $O(n^2)$ 复杂度降至 $O(n)$。

3.2 核心变量设计

参考原题解，解题需要维护以下状态：

• left、right：滑动窗口的左右边界，初始都指向字符串起始位置 0，窗口区间为[left, right)；
• counts：哈希表，记录当前窗口内每个字符出现的频数；
• count：整型计数器，记录当前窗口内不同字符的种类数；
• max_count：维护当前找到的最长合法子串长度；
• k = 2：本题允许的最大字符种类数。

其中，count计数器和counts频数哈希表协同工作：当某个字符频数从 0 变为 1 时说明窗口内引入新字符，count加 1；当某个字符频数减到 0 时说明该字符完全移出窗口，count减 1。

3.3 算法步骤

1. 初始化left = 0、right = 0、count = 0、max_count = 0，counts为空哈希表；
2. right指针不断向右移动：
   • 若counts[s[right]] == 0，说明s[right]是首次进入窗口的新字符，count += 1；
   • 将s[right]的频数加 1，right右移扩大窗口；
3. 若count > k（即窗口内字符种类数超过 2），说明当前窗口不合法，需要收缩左边界：
   • 若counts[s[left]] == 1，说明该字符移除后将彻底离开窗口，count -= 1；
   • 将s[left]的频数减 1，left右移缩小窗口；
   • 持续执行直到count <= k（由于每次只移除一个字符，这里用单次判断即可恢复合法）；
4. 窗口合法后，用max_count = max(max_count, right - left)更新答案；
5. 重复步骤 2～4，直到right遍历完整个字符串；
6. 返回max_count。

4. 代码实现

原题解给出的完整实现如下（为便于阅读，此处补充了行内注释，逻辑与原代码完全一致）：

import collections class Solution: def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int: max_count = 0 k = 2 # 最多允许的不同字符种类数 counts = collections.defaultdict(int) # 记录窗口内各字符频数 count = 0 # 当前窗口内的字符种类数 left, right = 0, 0 while right < len(s): # 新字符进入窗口：频数从 0 变为 1，种类数加 1 if counts[s[right]] == 0: count += 1 counts[s[right]] += 1 right += 1 # 窗口内字符种类数超过限制，收缩左边界 if count > k: if counts[s[left]] == 1: count -= 1 # 该字符将完全移出窗口 counts[s[left]] -= 1 left += 1 # 更新最长合法子串长度 max_count = max(max_count, right - left) return max_count

4.1 实现细节说明

为什么用collections.defaultdict(int)？仓库基础篇 哈希表 提到哈希表通过键直接访问值。defaultdict(int)在访问不存在的键时会自动以默认值 0 初始化，省去了「先判断键是否存在再赋值」的样板代码，这正是原题解导入collections模块的原因。

为什么单独维护count而不直接用len(counts)？本题写法中counts中某个字符频数减到 0 后仍然保留该键（值为 0），此时len(counts)统计的是「曾经出现过的字符总数」而非「当前窗口内实际存在的字符种类数」，因此必须用独立的count变量精确跟踪窗口内的活字符种类。这一点与 0340. 至多包含 K 个不同字符的最长子串 中「频数减到 0 时执行del window_counts[s[left]]再以len(window_counts)判断」的写法互为两种可行方案。

5. 复杂度分析

• 时间复杂度：$O(n)$。left和right指针各自最多移动 $n$ 次（$n$ 为字符串长度），整体为单趟线性扫描，远优于暴力枚举所有子串的 $O(n^2)$。
• 空间复杂度：$O(1)$。哈希表counts中最多同时存在 3 个键（当前窗口内的 2 种字符，加上收缩过程中可能短暂保留的已清零键），与字符串长度无关，可视为常数空间。

6. 算法执行过程演示

以演示字符串s = "eceba"为例，逐步跟踪窗口状态（counts仅列非零项）：

最终返回 3，即最长合法子串"ece"（长度 3，仅含e、c两种字符）。

7. 与仓库同类题的横向对比

本题是「滑动窗口 + 字符种类数约束」家族中的基础款，仓库中收录了多道同模板变体，建议对照学习：

其中 0340 题解 是本题最直接的推广——把k从常量变为入参，并把「频数归零即del键、以len(window_counts)判断种类数」的写法一并给出，两种写法均可通过测试，读者可自行体会取舍。

8. 通用化扩展：从「至多 2 种」到「至多 K 种」

将本题代码中的k = 2替换为函数参数，即可得到 K 版本的核心逻辑（完整实现见 0340 题解）：

def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int: ans = 0 window_counts = dict() left, right = 0, 0 while right < len(s): window_counts[s[right]] = window_counts.get(s[right], 0) + 1 while len(window_counts) > k: window_counts[s[left]] -= 1 if window_counts[s[left]] == 0: del window_counts[s[left]] left += 1 ans = max(ans, right - left + 1) right += 1 return ans

需要注意：当k增大、字符集复杂时，count > k后的收缩可能无法在单次移动left后立刻恢复合法，此时需要将「收缩」改写为while count > k循环（或反复判断len(window_counts) > k），这与 0003 无重复字符的最长子串 中while window[s[right]] > 1的收缩写法思路一致。

9. 延伸学习路径

• 滑动窗口基础概念、固定长度与不定长度窗口的算法步骤与代码模板，参见 滑动窗口算法；
• 仓库 滑动窗口题目列表 中整理了 20 余道滑动窗口题解（如 0438. 找到字符串中所有字母异位词、0076. 最小覆盖子串、1004. 最大连续1的个数 III 等），可按难度从简到难逐题刷练；
• 哈希表的原理、哈希函数设计与冲突处理，参见 哈希表基础；
• 本题题解收录于 0100-0199 题解索引，可通过该索引快速检索相邻编号题目的解法。

• 教程
• 文档
• 知识库