AlgoNote 题解：LeetCode 0159 至多包含两个不同字符的最长子串（哈希表 + 滑动窗口）

教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇基于「算法通关手册」AlgoNote 仓库中 0159. 至多包含两个不同字符的最长子串题解 展开系统讲解使用「滑动窗口 哈希表」在字符串上求「最多包含两种字符的最长连续子串」的完整思路、逐行代码与复杂度分析并延伸对比仓库中 0340. 至多包含 K 个不同字符的最长子串、0003. 无重复字符的最长子串 等同类滑动窗口问题帮助你掌握一类「不同字符/元素种类数受限」的区间问题通用解法。1. 题目信息题目编号0159LeetCode 159Premium 会员题标签哈希表、字符串、滑动窗口难度中等题目链接原题解文档中给出的题目链接为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 算法步骤初始化left 0、right 0、count 0、max_count 0counts为空哈希表right指针不断向右移动若counts[s[right]] 0说明s[right]是首次进入窗口的新字符count 1将s[right]的频数加 1right右移扩大窗口若count k即窗口内字符种类数超过 2说明当前窗口不合法需要收缩左边界若counts[s[left]] 1说明该字符移除后将彻底离开窗口count - 1将s[left]的频数减 1left右移缩小窗口持续执行直到count k由于每次只移除一个字符这里用单次判断即可恢复合法窗口合法后用max_count max(max_count, right - left)更新答案重复步骤 24直到right遍历完整个字符串返回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_count4.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仅列非零项步骤right 指向操作countscount窗口 [left, right)max_count1e加入 e{e:1}1[0,1)12c加入 c{e:1,c:1}2[0,2)23e加入 e{e:2,c:1}2[0,3)34b加入 bcount 超 2移除 s[0]e{e:1,c:1,b:1}2[1,4)35a加入 acount 超 2移除 s[1]c{c:0,e:1,b:1,a:1}2[2,5)3最终返回 3即最长合法子串ece长度 3仅含e、c两种字符。7. 与仓库同类题的横向对比本题是「滑动窗口 字符种类数约束」家族中的基础款仓库中收录了多道同模板变体建议对照学习题目仓库题解约束条件与本题的差异0159 至多包含两个不同字符的最长子串当前题解最多 2 种字符本题k固定为 20340 至多包含 K 个不同字符的最长子串题解文档最多 K 种字符将k 2泛化为参数k判断条件变为len(window_counts) k0003 无重复字符的最长子串题解文档每种字符至多 1 次约束为「任意字符频数 ≤ 1」收缩条件是window[s[right]] 10395 至少有 K 个重复字符的最长子串题解文档每种字符出现次数 ≥ K普通滑动窗口无法直接解决需枚举字符种类数i后配合less_k_count计数0904 水果成篮题解文档最多 2 种水果同一模板应用于数组收缩条件为len(window) 2答案取right - left 1其中 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 题解索引可通过该索引快速检索相邻编号题目的解法。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐AlgoNote 算法通关手册精讲LeetCode 0003 无重复字符的最长子串——哈希表 不定长滑动窗口AlgoNote 算法通关手册精讲LeetCode 0003 无重复字符的最长子串——哈希表 不定长滑动窗口 本文是「算法通关手册」AlgoNote 仓教程文档知识库LeetCode 0003 无重复字符的最长子串滑动窗口 哈希表解法全解析LeetCode 0003 无重复字符的最长子串滑动窗口 哈希表解法全解析 本篇技术指南以 leetcode 题解仓库中的 3.longest subst文档教程知识库AlgoNote 算法通关手册LeetCode 0030「串联所有单词的子串」——滑动窗口 哈希表完整题解AlgoNote 算法通关手册LeetCode 0030「串联所有单词的子串」——滑动窗口 哈希表完整题解 本文是 AlgoNote「算法通关手册」中 L教程文档知识库上一篇DataHub Ask DataHub 插件实战通过 BigQuery MCP Server 搭建对话式数据分析通道下一篇CKEditor 5 撤销/重做Undo/Redo功能深入解析批处理撤销栈、选择性撤销与命令 API创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考