LeetCode 3713. 最长的平衡子串1 详细技术解析（CSDN版）

LeetCode 3713. 最长的平衡子串1 详细技术解析CSDN版大家好今天给大家带来 LeetCode 3713. 最长的平衡子串1 的完整技术解析。本题是“平衡子串”系列的基础题型核心考察子串遍历、字符频次统计难度适中适合新手入门练习。与3714题仅含a/b/c不同本题字符串由所有小写英文字母组成约束更宽松n≤1000因此可采用“暴力枚举频次校验”的直观解法代码简洁易懂同时补充优化解法提升效率。本文将从题目解析、解题思路、代码实现、测试验证、易错点分析、总结拓展六个维度一步步讲透兼顾新手入门和代码规范要求完全贴合CSDN技术博客风格。一、题目深度解析精准吃透题意题目描述给你一个由小写英文字母组成的字符串 s。如果一个子串中所有不同字符出现的次数都相同则称该子串为平衡子串。请返回 s 的最长平衡子串的长度。关键约束划重点子串连续、非空的字符序列区别于子序列非连续无效平衡条件子串中所有不同字符的出现频次完全相等如“abba”中a、b各2次“zabc”中z、a、b、c各1次字符串范围仅由小写英文字母组成共26种可能字符数据规模1 ≤ s.length ≤ 1000n较小暴力解法可直接通过无需极致优化。示例解析直观理解平衡条件示例 1输入 s abbac 输出 4 解释最长的平衡子串是 abba因为不同字符 a 和 b 都恰好出现了 2 次。 补充其他可能的平衡子串有aba、b各1次、bb仅1种字符频次自然相等但长度均小于4。示例 2输入 s zzabccy 输出 4 解释最长的平衡子串是 zabc因为不同字符 z、a、b 和 c 都恰好出现了 1 次。 补充子串zzabz2次、a1次、b1次频次不等、abcca1次、b1次、c2次频次不等均非平衡子串。示例 3输入 s aba 输出 2 解释最长的平衡子串之一是 ab因为不同字符 a 和 b 都恰好出现了 1 次。另一个最长的平衡子串是 ba。 补充整个字符串aba中a2次、b1次频次不等因此不是平衡子串。核心难点提炼如何枚举所有可能的子串不遗漏、不重复如何快速统计子串中不同字符的频次并判断是否全部相等如何在保证正确性的前提下简化代码逻辑提升执行效率。二、解题思路两种解法从直观到优化结合本题n≤1000的约束提供两种解法暴力枚举法新手推荐直观易懂和优化枚举法高效版执行更快均能直接提交通过按需选择即可。解法1暴力枚举频次校验新手推荐直观易懂核心逻辑枚举所有可能的子串对每个子串统计字符频次判断是否满足平衡条件记录最长子串长度。步骤拆解初始化最长平衡子串长度max_len为1最小平衡子串为单个字符外层循环枚举子串起始下标i0 ≤ i n内层循环枚举子串结束下标jj ≥ i对当前子串s[i…j]用数组统计每个字符的出现频次26个小写字母用长度为26的数组存储提取频次数组中的非零值仅考虑子串中实际出现的字符判断所有非零值是否相等若相等计算当前子串长度j - i 1更新max_len遍历结束后返回max_len。时间复杂度O(n²×26) O(n²)双重循环枚举子串O(n²)每个子串统计频次O(26)可视为O(1)空间复杂度O(26) O(1)固定大小的频次数组与n无关优势逻辑直观、代码简洁无需复杂算法适合新手理解题意和平衡条件缺点执行效率一般但n1000时O(n²)1e6次操作可轻松通过测试。解法2优化枚举频次校验高效版核心优化避免重复统计子串频次内层循环扩展j时同步更新频次数组无需每次重新统计整个子串的频次提升执行效率。步骤拆解初始化最长平衡子串长度max_len为1外层循环枚举子串起始下标i0 ≤ i n初始化频次数组freq长度26初始值为0内层循环枚举子串结束下标jj ≥ i同步更新当前字符s[j]的频次freq[ord(s[j]) - ord(‘a’)] 1提取频次数组中的非零值判断所有非零值是否相等若相等计算当前子串长度j - i 1更新max_len遍历结束后返回max_len。时间复杂度O(n²)与暴力法一致但实际执行效率更高减少重复频次统计空间复杂度O(1)固定大小的频次数组优势在暴力法基础上优化执行更快代码逻辑仍简洁适合新手进阶缺点仍为O(n²)时间复杂度无本质提升但适配n1000的约束。复杂度对比清晰直观解题思路时间复杂度空间复杂度适用场景暴力枚举法O(n2)O(n^2)O(n2)O(1)O(1)O(1)新手理解题意、小规模字符串n≤1000优化枚举法O(n2)O(n^2)O(n2)O(1)O(1)O(1)新手进阶、追求更快执行速度三、代码实现严格符合题目要求格式带详细注释严格遵循 LeetCode 题目要求的 class Solution 格式提供两种解法均带详细注释可直接复制提交通过同时补充关键说明帮助新手理解。解法1暴力枚举频次校验新手推荐暴力枚举法可直接提交新手易懂class Solution: def longestBalanced(self, s: str) - int: n len(s) if n 0: return 0 max_len 1 # 最小平衡子串长度为1单个字符 # 双重循环枚举所有可能的子串 for i in range(n): for j in range(i, n): # 统计当前子串s[i..j]的字符频次 freq [0] * 26 # 索引0对应a25对应z for k in range(i, j1): char_idx ord(s[k]) - ord(a) freq[char_idx] 1 # 提取非零频次仅考虑子串中实际出现的字符 non_zero [cnt for cnt in freq if cnt 0] if not non_zero: continue # 子串为空跳过实际不会出现 # 判断所有非零频次是否相等 is_balanced True first non_zero[0] for cnt in non_zero[1:]: if cnt ! first: is_balanced False break # 更新最长平衡子串长度 if is_balanced: current_len j - i 1 if current_len max_len: max_len current_len return max_len解法2优化枚举频次校验高效版优化枚举法执行更快可直接提交class Solution: def longestBalanced(self, s: str) - int: n len(s) if n 0: return 0 max_len 1 # 外层循环枚举子串起始位置i for i in range(n): freq [0] * 26 # 每次重新初始化频次数组 # 内层循环扩展子串结束位置j同步更新频次 for j in range(i, n): char_idx ord(s[j]) - ord(a) freq[char_idx] 1 # 提取非零频次判断是否平衡 non_zero [cnt for cnt in freq if cnt 0] first non_zero[0] if all(cnt first for cnt in non_zero): # 满足平衡条件更新最长长度 current_len j - i 1 if current_len max_len: max_len current_len return max_len代码关键说明易错点标注频次数组映射用长度为26的数组freq对应26个小写英文字母通过 ord(s[k]) - ord(‘a’) 快速获取字符对应的索引高效统计频次非零频次筛选仅考虑子串中实际出现的字符非零频次避免将未出现的字符纳入判断如子串“ab”无需考虑’c’~z’的频次边界处理提前判断n0的情况虽题目约束n≥1但代码兼容空串场景初始化max_len为1避免单字符输入返回0的错误可提交性两种解法均严格遵循LeetCode的class Solution格式无多余代码复制后可直接提交通过所有测试点。四、测试用例验证全覆盖确保代码正确性以下测试用例覆盖示例场景、边界场景、特殊场景直接运行即可验证代码正确性可用于调试排查问题。完整测试用例含调试输出class Solution: def longestBalanced(self, s: str) - int: n len(s) if n 0: return 0 max_len 1 for i in range(n): freq [0] * 26 for j in range(i, n): char_idx ord(s[j]) - ord(a) freq[char_idx] 1 non_zero [cnt for cnt in freq if cnt 0] first non_zero[0] if all(cnt first for cnt in non_zero): current_len j - i 1 if current_len max_len: max_len current_len return max_len # 测试代码 if __name__ __main__: sol Solution() # 示例1输入 abbac → 输出 4预期4 test1 sol.longestBalanced(abbac) print(f示例1测试结果{test1}预期4) # 示例2输入 zzabccy → 输出 4预期4 test2 sol.longestBalanced(zzabccy) print(f示例2测试结果{test2}预期4) # 示例3输入 aba → 输出 2预期2 test3 sol.longestBalanced(aba) print(f示例3测试结果{test3}预期2) # 边界场景1单字符字符串 → 输出 1预期1 test4 sol.longestBalanced(a) print(f边界测试1{test4}预期1) # 边界场景2全相同字符 → 输出 5预期5 test5 sol.longestBalanced(aaaaa) print(f边界测试2{test5}预期5) # 特殊场景四种字符各1次 → 输出 4预期4 test6 sol.longestBalanced(abcd) print(f特殊测试{test6}预期4)运行结果所有测试用例均符合预期两种解法均可正常运行无报错、无逻辑漏洞可直接提交LeetCode通过。五、常见错误与避坑指南新手必看整理4个新手高频错误结合具体场景说明原因及解决方案避免踩坑提升代码提交通过率。**错误1忽略“单个字符是平衡子串”**场景初始化max_len为0输入sa时返回0不符合题目要求单个字符是平衡子串长度为1。解决方案max_len初始化为1确保单字符场景返回正确结果。错误2未筛选非零频次场景判断平衡时将频次数组中所有26个元素纳入判断包括未出现字符的0次频次导致误判如子串“ab”误将’c’~z’的0次纳入认为频次不相等。解决方案必须筛选出非零频次仅考虑子串中实际出现的字符再判断是否全部相等。错误3重复统计子串频次场景暴力法中每次枚举子串s[i…j]时重新统计整个子串的频次代码冗余、执行效率低。解决方案采用优化枚举法内层循环扩展j时同步更新频次避免重复统计。错误4边界处理遗漏场景未处理n0的情况虽题目约束n≥1但代码兼容空串可提升鲁棒性或ji时未统计子串单个字符。解决方案提前判断n0的情况内层循环j从i开始确保单个字符被统计。六、面试延伸与拓展提升文档价值助力面试本题虽难度适中但面试中常被追问延伸问题补充以下内容帮助大家应对面试提问提升竞争力。延伸1若字符串长度扩大到1e5如何优化解答本题n≤1000暴力法可通过若n扩大到1e5O(n²)解法会超时需采用“滑动窗口哈希表”优化时间复杂度降至O(n)。核心思路维护滑动窗口用哈希表统计窗口内字符频次判断平衡条件动态扩张和收缩窗口记录最长平衡子串长度。延伸2如何输出最长平衡子串的具体内容而非长度解答在遍历过程中记录最长平衡子串的起始和结束下标遍历结束后截取子串即可。修改优化枚举法代码新增start和end变量记录下标延伸输出最长平衡子串具体内容class Solution: def longestBalancedSubstring(self, s: str) - str: n len(s) if n 0: return max_len 1 start end 0 # 记录最长子串的起始和结束下标 for i in range(n): freq [0] * 26 for j in range(i, n): char_idx ord(s[j]) - ord(a) freq[char_idx] 1 non_zero [cnt for cnt in freq if cnt 0] first non_zero[0] if all(cnt first for cnt in non_zero): current_len j - i 1 if current_len max_len: max_len current_len start i end j # 截取最长平衡子串 return s[start:end1]延伸3如何统计所有平衡子串的数量解答在遍历过程中新增一个计数器count每次判断子串平衡时count 1遍历结束后返回count即可无需记录最长长度只需统计次数。七、总结核心考点刷题建议核心考点回顾基础能力子串的枚举方法、字符频次统计26个小写英文字母的映射核心思维暴力枚举的直观性、优化枚举的效率提升理解“平衡子串”的核心条件边界处理单字符、全相同字符、多字符等场景的兼容。刷题建议新手入门先实现暴力枚举法理解平衡子串的判断逻辑调试示例用例和边界场景掌握频次统计的方法进阶练习实现优化枚举法理解“同步更新频次”的优化思路提升代码执行效率面试准备掌握延伸问题滑动窗口优化、输出子串内容应对面试官追问提升竞争力。本题是平衡子串系列的基础题型掌握本题的频次统计和子串枚举思路可轻松应对后续更复杂的平衡子串问题如仅含3种字符、子序列平衡等。如果本文对你有帮助欢迎点赞、收藏、转发我会持续更新 LeetCode 题解从基础到进阶助力大家高效刷题、轻松面试~