LeetCode 696. 计数二进制子串（详细解析 + 多解法实现）

LeetCode 696. 计数二进制子串详细解析 多解法实现前言LeetCode 696. 计数二进制子串是一道经典的字符串处理题目难度中等核心考察对字符串分组、规律提炼的能力。本题看似简单但如果暴力求解会超时因此需要找到高效的解题思路。本文将从题目分析、思路推导、代码实现基础版优化版、复杂度分析、常见坑点等方面全面拆解这道题帮你彻底吃透解题逻辑同时适配CSDN技术博客的实战风格附完整可运行代码和测试案例。适用人群算法入门者、字符串处理学习者、LeetCode刷题爱好者适合巩固字符串分组和贪心思想的应用。核心目录题目核心解析题干拆解 示例分析解题思路推导暴力法 → 优化法循序渐进代码实现Python严格遵循题干给定类结构复杂度分析时间 空间常见坑点与避坑技巧拓展思考同类题目延伸一、题目核心解析1.1 题干拆解题目给定一个仅由 ‘0’ 和 ‘1’ 组成的字符串 s要求统计满足以下两个条件的非空连续子串数量子串中 0 和 1 的数量相等子串中的所有 0 成组连续、所有 1 成组连续即不会出现 010、101 这类交叉情况。关键补充重复出现的子串不同位置需分别统计例如示例1中“01”出现两次均计入总数。1.2 示例深度分析示例1输入 s “00110011”输出 6满足条件的子串拆解“0011”0的数量21的数量2且0连续、1连续“01”从第2个0和第1个1组成0和1各1个连续分组“1100”1的数量20的数量2连续分组“10”从第2个1和第1个0组成各1个连续分组“0011”从第3个0和第3个1组成各2个连续分组“01”从第4个0和第4个1组成各1个连续分组。注意“00110011” 不满足条件因为0和1交叉出现00→11→00→11并非所有0连续、所有1连续。示例2输入 s “10101”输出 4满足条件的子串“10”第1-2位、“01”第2-3位、“10”第3-4位、“01”第4-5位均为1和0各1个且连续分组。1.3 题干隐含规律通过示例分析可提炼核心规律满足条件的子串本质是相邻两个不同字符分组的“交集”——假设相邻两组的长度分别为 m 和 n那么这两组可组成 min(m, n) 个满足条件的子串。例如“0011” 分为 [2, 2]0的长度21的长度2min(2,2)2对应子串 “01” 和 “0011”“10101” 分为 [1,1,1,1,1]相邻两组 min 均为1共4个11114。二、解题思路推导解题思路分两步先提炼字符分组长度再根据分组长度计算满足条件的子串数量。我们从暴力法入手逐步优化到最优解法理解每一步的优化逻辑。2.1 暴力法思路简单超时警告思路遍历所有可能的子串判断每个子串是否满足“0和1数量相等”且“分组连续”两个条件统计符合条件的子串个数。具体步骤遍历字符串的所有起始位置 i0 ≤ i len(s)遍历所有结束位置 ji1 ≤ j len(s)确保子串非空且长度为偶数因为0和1数量相等截取子串 s[i…j]判断是否满足① 0和1数量相等② 所有0连续、所有1连续统计符合条件的子串数量。局限性时间复杂度 O(n²)n 为字符串长度。当 n 10⁵ 时题干提示上限运算量达到 10¹⁰远超时间限制必然超时。因此暴力法仅适用于理解题目实际刷题需优化。2.2 优化法分组统计 贪心最优解法核心思路利用“相邻分组 min(m,n) 贡献子串数”的规律先将字符串按连续相同字符分组再遍历分组数组累加相邻两组的 min 值即为最终答案。具体步骤核心分组统计将字符串 s 按连续相同字符拆分记录每组的长度得到分组数组 counts。例如s “00110011” → 分组为 [2, 2, 2, 2]00→211→200→211→2s “10101” → 分组为 [1,1,1,1,1]。计算结果遍历 counts 数组对于每一个 i1 ≤ i len(counts)累加 min(counts[i-1], counts[i])总和即为满足条件的子串数量。逻辑验证结合示例1counts [2,2,2,2]遍历过程i1min(2,2)2 → 累加 2对应 “01”、“0011”i2min(2,2)2 → 累加 2对应 “10”、“1100”i3min(2,2)2 → 累加 2对应 “01”、“0011”总和2226与示例1输出一致。优势时间复杂度 O(n)仅需遍历字符串2次1次分组1次计算空间复杂度 O(n)最坏情况如字符串全为交替字符分组数组长度为n可优化至 O(1)无需存储完整分组数组仅记录前一组长度。三、代码实现Python严格遵循题干给定的类结构实现两种版本基础分组版 空间优化版附详细注释可直接复制到LeetCode提交。3.1 基础版本分组数组易理解核心先构建分组数组再累加相邻 min 值代码简洁易懂适合入门。classSolution:defcountBinarySubstrings(self,s:str)-int:# 特殊情况字符串长度为1无满足条件的子串iflen(s)2:return0# 步骤1分组统计连续字符的长度counts[]current_chars[0]# 当前连续字符current_count1# 当前连续字符的长度forcins[1:]:ifccurrent_char:# 字符相同累加长度current_count1else:# 字符不同将当前长度加入分组更新当前字符和长度counts.append(current_count)current_charc current_count1# 循环结束后将最后一组长度加入分组数组counts.append(current_count)# 步骤2遍历分组数组累加相邻两组的min值result0foriinrange(1,len(counts)):resultmin(counts[i-1],counts[i])returnresult3.2 优化版本空间O(1)高效核心无需存储完整分组数组仅记录前一组的长度prev_count遍历过程中实时计算节省空间。修正说明原错误在于初始时将prev_count设为1第一组长度导致首次字符切换时误将“第一组与自身”计算一次多算1个结果修正后prev_count初始为0避免该问题确保结果正确。classSolution:defcountBinarySubstrings(self,s:str)-int:# 特殊情况字符串长度小于2直接返回0iflen(s)2:return0result0prev_count0# 修正初始前一组长度设为0第一组无前一组不贡献结果current_chars[0]current_count1# 当前组连续字符的长度forcins[1:]:ifccurrent_char:# 字符相同当前组长度累加current_count1else:# 字符不同累加前一组和当前组的min值仅当prev_count不为0时resultmin(prev_count,current_count)# 更新前一组长度为当前组长度重置当前组prev_countcurrent_count current_charc current_count1# 循环结束后处理最后一组和前一组的min值resultmin(prev_count,current_count)returnresult3.3 测试案例验证将示例1、示例2代入代码验证结果正确性# 测试示例1s100110011print(Solution().countBinarySubstrings(s1))# 输出6修正后符合预期# 测试示例2s210101print(Solution().countBinarySubstrings(s2))# 输出4正常# 额外测试用例s3000111print(Solution().countBinarySubstrings(s3))# 输出3正常s401print(Solution().countBinarySubstrings(s4))# 输出1正常s50print(Solution().countBinarySubstrings(s5))# 输出0正常四、复杂度分析4.1 基础版本时间复杂度O(n)n 为字符串长度。遍历字符串1次完成分组遍历分组数组1次完成计算两次遍历均为 O(n)。空间复杂度O(n)最坏情况如 s “010101…”分组数组长度为n占用 O(n) 空间。4.2 优化版本时间复杂度O(n)仅遍历字符串1次实时计算结果无额外遍历。空间复杂度O(1)仅使用常数个变量prev_count、current_count、current_char、result不占用额外空间。总结优化版本在时间和空间上均为最优适合处理题干中 n10⁵ 的极端情况推荐优先使用。五、常见坑点与避坑技巧坑点1忽略“连续分组”条件误将交叉子串计入如 “010” 视为有效子串。避坑牢记“所有0连续、所有1连续”核心是“相邻分组”而非整个子串中0和1数量相等即可。坑点2循环结束后忘记将最后一组长度加入分组数组基础版本或忘记处理最后一组与前一组的min值优化版本。避坑分组统计时循环结束后必须补充最后一组的长度否则会遗漏最后一组与前一组的贡献。坑点3特殊情况未处理如字符串长度为1导致索引越界或计算错误。避坑开头添加判断若 len(s) 2直接返回0避免无效计算。坑点4暴力法超时未想到分组统计的规律。避坑遇到字符串连续字符统计类问题优先考虑“分组”思路提炼规律避免暴力遍历。六、拓展思考6.1 同类题目延伸本题的分组统计思路可迁移到以下同类题目核心都是“连续字符分组 规律提炼”LeetCode 485. 最大连续1的个数统计连续1的最大长度分组后取最大值即可LeetCode 1446. 连续字符统计字符串中连续相同字符的最大长度分组后取最大值LeetCode 1209. 删除字符串中的所有相邻重复项 II分组后删除长度≥k的分组再重构字符串。6.2 思路拓展本题的优化思路本质是“贪心”——每一步都累加当前相邻两组的贡献无需回溯符合贪心算法“局部最优→全局最优”的特点。在字符串处理中遇到“连续分组”“相邻对比”类问题均可尝试贪心思想简化计算。七、总结LeetCode 696. 计数二进制子串的核心的是“分组统计连续字符长度”通过提炼“相邻分组 min(m,n) 贡献子串数”的规律将时间复杂度从 O(n²) 优化到 O(n)空间复杂度可优化至 O(1)。解题关键先拆分字符串为连续字符分组记录每组长度累加相邻两组的 min 值即为最终答案注意处理特殊情况和循环结束后的边界问题避免遗漏。