LeetCode 3714. 最长的平衡子串2 题解 —— 分类讨论 + 前缀和 + 哈希表

LeetCode 3714. 最长的平衡子串2 题解 —— 分类讨论 前缀和 哈希表大家好今天给大家带来 LeetCode 中等难度题目——3714. 最长的平衡子串2 的详细题解。本题核心考察字符频次统计、分类讨论思维以及前缀和差值哈希表的优化技巧。由于字符串仅包含 ‘a’、‘b’、‘c’ 三种字符我们可以通过分类拆解问题将复杂的平衡子串判断转化为可高效求解的子问题最终实现 O(n) 时间复杂度轻松适配 1e5 级别的数据规模。本文将从题目描述、解题思路、代码实现、复杂度分析、测试验证、总结拓展六个维度一步步讲透解题逻辑兼顾新手易懂性和面试进阶需求。一、题目描述精准提炼规避理解偏差给定一个只包含字符a、b和c的字符串s。如果一个子串中所有不同字符出现的次数都相同则称该子串为平衡子串。请返回s的最长平衡子串的长度。关键说明子串是字符串中连续的、非空的字符序列区别于子序列非连续这是解题的核心前提。示例解析直观理解题意示例 1输入s abbac 输出4 解释最长的平衡子串是 abba因为不同字符 a 和 b 都恰好出现了 2 次。示例 2输入s aabcc 输出3 解释最长的平衡子串是 abc因为不同字符 a、b 和 c 都恰好出现了 1 次。示例 3输入s aba 输出2 解释最长的平衡子串之一是 ab因为不同字符 a 和 b 都恰好出现了 1 次。另一个最长的平衡子串是 ba。题目提示明确约束条件1 ≤ s.length ≤ 10⁵需保证算法时间复杂度高效避免 O(n²) 超时s 仅包含字符 ‘a’、‘b’、‘c’核心约束为分类讨论提供依据。二、解题思路分类讨论 前缀和 哈希表清晰高效本题的核心难点的是如何快速判断子串中所有不同字符的频次相等同时高效找到最长子串。由于字符串仅包含 3 种字符我们可以按子串中包含的字符种类数进行分类讨论将复杂问题拆解为 3 个简单子问题分别求解后取最大值即可。核心思路将平衡子串分为「单字符」「双字符」「三字符」三种情况每种情况采用对应的高效解法最终汇总结果确保时间复杂度 O(n)适配 1e5 长度的字符串。1. 情况1只包含 1 种字符最简单场景逻辑若子串中仅包含一种字符如 “aaaa”、“bbbb”则该子串必然是平衡子串只有一种不同字符频次自然相等。解法直接遍历字符串统计每一段连续相同字符的长度记录最大值即可。时间复杂度O(n)空间复杂度O(1)仅需两个变量记录当前连续长度和最大长度。2. 情况2恰好包含 2 种字符且频次相等逻辑子串中只能出现指定的两种字符第三种字符不能出现且这两种字符的出现次数必须完全相等如 “abba” 中 ‘a’ 和 ‘b’ 各 2 次。核心组合由于只有 3 种字符双字符组合共 3 种(a,b)、(a,c)、(b,c)每种组合的处理逻辑完全对称。解法前缀和差值 哈希表以组合 (a,b) 为例维护两个计数器 cnt_a、cnt_b分别记录当前遍历到的 ‘a’ 和 ‘b’ 的数量计算差值 diff cnt_a - cnt_b差值恒定意味着 cnt_a cnt_b满足频次相等条件用哈希表记录每个 diff 第一次出现的位置若后续再次遇到相同 diff说明两个位置之间的子串满足 cnt_a cnt_b若遇到第三种字符如组合 (a,b) 中遇到 ‘c’则重置状态计数器清零、哈希表重置因为包含第三种字符的子串不符合要求遍历过程中不断更新最长子串长度。时间复杂度O(n)每种组合遍历一次字符串空间复杂度O(n)哈希表最坏情况存储 n 个差值状态。3. 情况3包含全部 3 种字符且频次相等逻辑子串中必须同时出现 ‘a’、‘b’、‘c’ 三种字符且三种字符的出现次数完全相等如 “abc” 中各 1 次“aabbcc” 中各 2 次。解法前缀和差值 哈希表通过差值转化频次相等条件维护三个计数器 cnt_a、cnt_b、cnt_c分别记录三种字符的数量定义两个差值d1 cnt_b - cnt_ad2 cnt_c - cnt_b若 cnt_a cnt_b cnt_c则必然有 d1 0 且 d2 0用哈希表记录 (d1, d2) 第一次出现的位置初始时在 -1 位置记录 (0, 0)对应空串状态每次更新计数器后计算 (d1, d2)若该差值对已存在于哈希表说明两个位置之间的子串满足三种字符频次相等遍历过程中更新最长子串长度。关键说明该方法自动保证三种字符均出现——若某一种字符未出现三者频次相等的唯一可能是均为 0空串而非空子串必然满足三种字符频次均大于 0因此无需额外判断。时间复杂度O(n)空间复杂度O(n)哈希表存储差值对状态。整体流程汇总求解计算「单字符」场景的最长平衡子串长度 ans1分别计算 3 种「双字符组合」的最长平衡子串长度取最大值 ans2计算「三字符」场景的最长平衡子串长度 ans3最终答案为 max(ans1, ans2, ans3)。三、代码实现完整可提交带详细注释严格遵循 LeetCode 题目要求的 class Solution 格式代码结构清晰关键步骤添加注释兼顾可读性和可提交性可直接复制到 LeetCode 提交通过。完整可提交代码分类讨论前缀和哈希表class Solution: def longestBalanced(self, s: str) - int: n len(s) if n 0: return 0 ans 0 # ---------- 1. 只有一种字符最长连续相同字符 ---------- max_single 1 cur_len 1 for i in range(1, n): if s[i] s[i-1]: cur_len 1 max_single max(max_single, cur_len) else: cur_len 1 ans max(ans, max_single) # ---------- 2. 恰好两种字符且频次相等 ---------- def max_two_chars(c1, c2, c3): # 只包含 c1 和 c2不能出现 c3返回该组合的最长平衡子串长度 cnt1 cnt2 0 # 哈希表key差值(cnt1 - cnt2)value第一次出现的下标 pos {0: -1} max_len 0 for i, ch in enumerate(s): if ch c3: # 遇到第三种字符重置所有状态计数器、哈希表 cnt1 cnt2 0 pos {0: i} # 新子串从i1开始当前i位置差值为0 elif ch c1: cnt1 1 diff cnt1 - cnt2 if diff in pos: # 差值相同说明两位置之间cnt1 cnt2 max_len max(max_len, i - pos[diff]) else: # 首次出现该差值记录下标 pos[diff] i elif ch c2: cnt2 1 diff cnt1 - cnt2 if diff in pos: max_len max(max_len, i - pos[diff]) else: pos[diff] i return max_len # 分别处理三种双字符组合更新答案 ans max(ans, max_two_chars(a, b, c)) ans max(ans, max_two_chars(a, c, b)) ans max(ans, max_two_chars(b, c, a)) # ---------- 3. 包含三种字符且频次相等 ---------- cnt_a cnt_b cnt_c 0 # 哈希表key(d1, d2)value第一次出现的下标初始状态(0,0)对应下标-1 pos {(0, 0): -1} for i, ch in enumerate(s): # 更新对应字符的计数器 if ch a: cnt_a 1 elif ch b: cnt_b 1 else: cnt_c 1 # 计算两个差值判断是否满足三种字符频次相等 d1 cnt_b - cnt_a d2 cnt_c - cnt_b if (d1, d2) in pos: # 差值对相同说明两位置之间cnt_a cnt_b cnt_c ans max(ans, i - pos[(d1, d2)]) else: # 首次出现该差值对记录下标 pos[(d1, d2)] i return ans代码关键说明易错点标注单字符场景初始化 cur_len 为 1最小平衡子串长度为 1避免单字符输入如 “a”返回 0 的错误双字符场景遇到第三种字符时必须重置状态否则会包含无效字符导致判断错误哈希表初始值 {0: -1} 是为了处理“从字符串起始位置开始的子串”如 “ab”i1 时 diff0对应 pos[0]-1长度为 2三字符场景哈希表初始值 {(0,0): -1} 对应空串状态确保从起始位置开始的有效子串如 “abc”能正确计算长度差值 d1 和 d2 的设计是核心将“三者相等”转化为“两个差值均为 0”简化判断逻辑边界处理提前判断 n0 的情况虽题目约束 n≥1但代码兼容空串场景确保代码鲁棒性。四、复杂度分析清晰直观助力面试维度具体分析复杂度时间复杂度共进行 4 次线性遍历1 次单字符、3 次双字符、1 次三字符合计常数次每次遍历 O(n)哈希表操作插入、查询均为 O(1)因此总时间复杂度为 O(n)。O(n)O(n)O(n)空间复杂度主要为哈希表的存储开销最坏情况下所有差值/差值对均不重复哈希表需存储 n 个状态因此空间复杂度为 O(n)其他计数器均为常数空间可忽略。O(n)O(n)O(n)优化说明本题空间复杂度无法进一步优化哈希表是实现 O(n) 时间复杂度的必要条件但在实际运行中由于字符种类固定3种差值/差值对的数量有限实际空间开销远小于 O(n)。五、测试验证全覆盖确保代码正确性以下测试用例覆盖示例场景、边界场景、特殊场景直接运行即可验证代码正确性可用于调试排查问题确保提交后无报错、无逻辑漏洞。完整测试用例含调试输出class Solution: def longestBalanced(self, s: str) - int: n len(s) if n 0: return 0 ans 0 # 1. 只有一种字符 max_single 1 cur_len 1 for i in range(1, n): if s[i] s[i-1]: cur_len 1 max_single max(max_single, cur_len) else: cur_len 1 ans max(ans, max_single) # 2. 恰好两种字符且频次相等 def max_two_chars(c1, c2, c3): cnt1 cnt2 0 pos {0: -1} max_len 0 for i, ch in enumerate(s): if ch c3: cnt1 cnt2 0 pos {0: i} elif ch c1: cnt1 1 diff cnt1 - cnt2 if diff in pos: max_len max(max_len, i - pos[diff]) else: pos[diff] i elif ch c2: cnt2 1 diff cnt1 - cnt2 if diff in pos: max_len max(max_len, i - pos[diff]) else: pos[diff] i return max_len ans max(ans, max_two_chars(a, b, c)) ans max(ans, max_two_chars(a, c, b)) ans max(ans, max_two_chars(b, c, a)) # 3. 包含三种字符且频次相等 cnt_a cnt_b cnt_c 0 pos {(0, 0): -1} for i, ch in enumerate(s): if ch a: cnt_a 1 elif ch b: cnt_b 1 else: cnt_c 1 d1 cnt_b - cnt_a d2 cnt_c - cnt_b if (d1, d2) in pos: ans max(ans, i - pos[(d1, d2)]) else: pos[(d1, d2)] i return ans # 测试代码 if __name__ __main__: sol Solution() # 示例1输入 abbac → 输出 4预期4 test1 sol.longestBalanced(abbac) print(f示例1测试结果{test1}预期4) # 示例2输入 aabcc → 输出 3预期3 test2 sol.longestBalanced(aabcc) print(f示例2测试结果{test2}预期3) # 示例3输入 aba → 输出 2预期2 test3 sol.longestBalanced(aba) print(f示例3测试结果{test3}预期2) # 边界场景1单字符字符串 → 输出 4预期4 test4 sol.longestBalanced(aaaa) print(f边界测试1{test4}预期4) # 边界场景2三种字符各出现2次 → 输出 6预期6 test5 sol.longestBalanced(aabbcc) print(f边界测试2{test5}预期6) # 特殊场景三种字符交替出现 → 输出 6预期6 test6 sol.longestBalanced(abcabc) print(f特殊测试1{test6}预期6) # 特殊场景双字符交替出现 → 输出 4预期4 test7 sol.longestBalanced(abab) print(f特殊测试2{test7}预期4)运行结果所有测试用例均符合预期代码可正常运行无报错、无逻辑漏洞可直接提交 LeetCode 通过所有测试点。六、常见错误与避坑指南新手必看整理 4 个新手高频错误结合具体场景说明原因及解决方案避免踩坑提升代码提交通过率。错误1单字符场景初始化 cur_len 为 0场景输入 s “a” 时cur_len 初始为 0最终返回 0不符合“单字符是平衡子串”的逻辑。解决方案cur_len 和 max_single 均初始化为 1确保单字符场景返回正确结果。错误2双字符场景未重置状态场景处理组合 (a,b) 时遇到 ‘c’ 未重置计数器和哈希表导致后续子串包含 ‘c’ 仍被判断出现错误结果。解决方案遇到第三种字符时必须将 cnt1、cnt2 清零哈希表重置为 {0: i}确保新子串不包含无效字符。错误3三字符场景哈希表未初始化 (0,0): -1场景输入 s “abc” 时i2 时 (d1, d2) (0,0)若哈希表无初始值无法计算长度2 - (-1) 3导致错过正确结果。解决方案哈希表初始化为 {(0, 0): -1}适配从字符串起始位置开始的有效子串。错误4混淆子串与子序列场景误将非连续的字符序列当作子串如 s “abbac” 中误将 “abac” 当作子串判断导致逻辑错误。解决方案牢记子串是连续的字符序列遍历过程中始终维护连续区间不考虑非连续情况。七、面试延伸与拓展提升文档价值助力面试本题是面试中的高频中等题核心考察分类讨论思维和前缀和哈希表的优化技巧以下延伸问题可帮助大家拓展思维应对面试追问。延伸1若字符串包含 k 种字符k3如何优化算法解答核心思路不变仍采用分类讨论单字符场景与本题一致统计最长连续相同字符长度双字符场景枚举所有 C(k,2) 种双字符组合每种组合采用“前缀和差值哈希表”处理时间复杂度 O(k×n)k 字符场景需保证所有 k 种字符频次相等可通过“多差值”如 d1 cnt2 - cnt1, d2 cnt3 - cnt1, …, dk-1 cntk - cnt1用哈希表记录差值组合的第一次出现位置时间复杂度 O(n)。注当 k 较大时如 k26双字符场景的时间复杂度会升高需结合实际场景优化如仅考虑出现频次较高的字符组合。延伸2如何输出最长平衡子串的具体内容而非长度解答在遍历过程中记录最长平衡子串的起始和结束下标遍历结束后截取子串即可。关键修改点新增 start 和 end 变量初始化为 0每次更新 ans 时同步更新 start 和 end如 i - pos[diff] ans 时start pos[diff] 1end i遍历结束后返回 s[start:end1]。延伸3如何处理“子序列”而非“子串”的平衡问题解答子序列可非连续解题思路完全不同需使用回溯法或动态规划回溯法枚举所有可能的子序列统计字符频次判断是否平衡时间复杂度 O(2^n)仅适合小规模字符串动态规划定义 dp[i][a][b][c] 表示前 i 个字符中a、b、c 出现次数分别为 a、b、c 时的最长子序列长度时间复杂度 O(n×max_cnt³)max_cnt 为字符最大出现次数适合中等规模字符串。八、总结核心考点刷题建议核心考点回顾分类讨论思维将复杂问题拆解为单字符、双字符、三字符三种场景逐一求解降低解题难度前缀和差值技巧将“频次相等”转化为“差值恒定”简化判断逻辑降低时间复杂度哈希表应用记录差值/差值对的第一次出现位置快速计算符合条件的子串长度是实现 O(n) 时间复杂度的核心边界处理能力处理单字符、空串、第三种字符等边界场景确保代码鲁棒性。刷题建议新手优先掌握分类讨论的思路理解每种场景的解题逻辑重点吃透“前缀和差值哈希表”的核心原理动手实现代码调试示例用例和边界场景避免踩坑如状态重置、哈希表初始化结合延伸问题练习拓展思维应对面试中的追问提升竞争力同类题目拓展LeetCode 1248. 统计优美子数组、LeetCode 904. 水果成篮均为“子串计数哈希表”的经典应用可同步练习巩固。本题是“多字符频次平衡”问题的典型代表分类讨论前缀和哈希表的解题思路具有通用性掌握后可快速应对同类题目。如果本文对你有帮助欢迎点赞、收藏、转发我会持续更新 LeetCode 题解从基础到进阶助力大家高效刷题、轻松面试~