计数二进制子串

• https://leetcode.cn/problems/count-binary-substrings/

描述

• 给定一个字符串 s，统计并返回具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是成组连续的。

• 重复出现（不同位置）的子串也要统计它们出现的次数。

示例 1：

输入：s = "00110011" 输出：6 解释：6 个子串满足具有相同数量的连续 1 和 0 ："0011"、"01"、"1100"、"10"、"0011" 和 "01" 。 注意，一些重复出现的子串（不同位置）要统计它们出现的次数。 另外，"00110011" 不是有效的子串，因为所有的 0（还有 1 ）没有组合在一起。

示例 2：

输入：s = "10101" 输出：4 解释：有 4 个子串："10"、"01"、"10"、"01" ，具有相同数量的连续 1 和 0 。

提示

• 1 <= s.length <=10510^5105
• s[i] 为 ‘0’ 或 ‘1’

Typescript 版算法实现

1 ）方案1

// leetcode 大规模数据不通过functioncountBinarySubstrings(s:string):number{// 建立数据结构，队列，用于保存数据constr=[]// 给定任意子输入都返回第一个符合条件的子串constmatch=(s:string)=>{// 找到含有0或1一次或多次的匹配字符串constj:string=s.match(/^(0+|1+)/)?.[0]??''// 生成第一个字符异或得到相反的字符，并且长度和匹配字符串保持一致consto:string=(Number(j[0])^1).toString().repeat(j.length)// 构造出新的正则，用于过滤当前切片的规则，注意这里的 ^ 开始很重要constreg=newRegExp(`^(${j}${o})`)// 符合条件，拿到 () 中的匹配字符串if(reg.test(s)){returnRegExp.$1// 得到第 1 个子表达式相匹配的文本}return''}// 通过for循环控制程序运行的流程for(leti=0,len=s.length-1;i<len;i++){// i 递增，进行切片处理，每次 slice 都会向后移动一位// 注意 slice 左闭右开，参数为：[start, end]constsub=match(s.slice(i))if(sub){r.push(sub)}}returnr.length};console.log(countBinarySubstrings('00110011'))

思路：

• 对字符串做切片处理，从第一位到倒数第二位，左闭右开，此处需要一个for循环
• 对每一个切片进行单一处理，每个切片只找一个，避免循环到后面出现重复
• 将找到符合规则的切片存入数组
• 统计最终数组的长度，即答案

注意：

• 这个方案在 leetcode上是通不过的，错误发生在 new RegExp 的时候，错误信息是：SyntaxError: Invalid regular expression，Regular expression too large 这个错误在实际应用场景中是不会出现的，用例有些极端了
• 拼接出的正则表达式 ^(j{j}j{o}) 会超出引擎的处理限制，导致 RangeError 或性能崩溃

2 ）方案2

functioncountBinarySubstrings2(s:string):number{letcount:number=0// 用于统计最终符合要求的长度letlast:string='_';// 上一个字符初始化letpre:number=0;// 上一次统计次数letcur:number=0;// 当前字符出现的统计次数leti:number=0;// 当前循环次数while(i<=s.length){constc:string=s[i];// 获取当前切片字符串// 第一次一定会执行，last 就会被重新赋值，last 保留的是前一个字符// 只有遇到新的值时，last 才会变成当前新值，这个if里面对当前字符 c 进行统计次数if(last!==c){// 遇到下一个不同字符更新, 用pre保留cur值last=c;// 保留当前字符串count+=Math.min(pre,cur);// 比较前2个不同字符出现次数的最小值pre=cur;// pre 保留前一个字符出现的次数cur=0;// 如果不相等，cur 统计次数清零// console.log('count；', count);}cur++;// 统计当前字符出现的次数i++;// 本次循环次数+1}returncount;}console.log(countBinarySubstrings2('00110011'));

• 这是官方精选解题方案
  • https://leetcode.cn/problems/count-binary-substrings/solution/count-binary-substrings-by-ikaruga/
• 这样前面是连续 0/1 后面是连续 1/0 的数据
• 每次符合的字符取决于前面 0/1 的个数和后面 1/0 的个数，即 min(pre, cur)
• 遍历时，当数字再一次改变时（或到达结尾时）, 意味着一段结束，并能得到这一段前面和后面数字的个数
• 每次符合条件，并采用最小值，即可得到当前可用的统计答案
• 再将结果累加到 count 上就得到所有的可能结果

3 ）方案3

functioncountBinarySubstrings3(s:string):number{// index 是当前循环次数, n 是字符串长度, last是上一次统计数量, ans 是最终统计结果letindex=0,n=s.length,last=0,ans=0;while(index<n){constc=s.charAt(index);// c 是当前字符串letcount=0;// 每次count都重置一下// 统计当前相同字符串的结果while(index<n&&s.charAt(index)===c){++index;++count;}ans+=Math.min(count,last);// 从 count 和 last 找到最小的统计，取最小值last=count;// 缓存 count统计}returnans;};console.log(countBinarySubstrings3("00110011"));

• 此方案为官方题解，参考：
• https://leetcode.cn/problems/count-binary-substrings/solutions/367704/ji-shu-er-jin-zhi-zi-chuan-by-leetcode-solution/
• 此方案与上述方案2有异曲同工之妙，两者原理相似

Python3 版算法实现

1 ）方案1

classSolution:defcountBinarySubstrings(self,s:str)->int:count=0# 用于统计最终符合要求的长度last='_'# 上一个字符初始化pre=0# 上一次统计次数cur=0# 当前字符出现的统计次数i=0# 当前循环次数whilei<=len(s):ifi==len(s):c=Noneelse:c=s[i]# 获取当前切片字符串# 第一次一定会执行，last 就会被重新赋值，last 保留的是前一个字符# 只有遇到新的值时，last 才会变成当前新值，这个if里面对当前字符 c 进行统计次数iflast!=c:# 遇到下一个不同字符更新, 用pre保留cur值last=c# 保留当前字符串count+=min(pre,cur)# 比较前2个不同字符出现次数的最小值pre=cur# pre 保留前一个字符出现的次数cur=0# 如果不相等，cur 统计次数清零cur+=1# 统计当前字符出现的次数i+=1# 本次循环次数+1returncount

2 ）方案2

classSolution:defcountBinarySubstrings(self,s:str)->int:index=0# 当前循环次数n=len(s)# 字符串长度last=0# 上一次统计数量ans=0# 最终统计结果whileindex<n:c=s[index]# 获取当前字符串count=0# 重置每次统计的计数# 统计当前相同字符串的结果whileindex<nands[index]==c:index+=1count+=1ans+=min(count,last)# 从 count 和 last 找到最小的统计值，取最小值进行累加last=count# 缓存 count 统计值returnans

Golang 版算法实现

1 ）方案1

funccountBinarySubstrings(sstring)int{count:=0// 用于统计最终符合要求的长度last:=byte('_')// 上一个字符初始化pre:=0// 上一次统计次数cur:=0// 当前字符出现的统计次数i:=0// 当前循环次数fori<=len(s){varcbyteifi==len(s){c=0}else{c=s[i]// 获取当前切片字符串}// 第一次一定会执行，last 就会被重新赋值，last 保留的是前一个字符// 只有遇到新的值时，last 才会变成当前新值，这个if里面对当前字符 c 进行统计次数iflast!=c{// 遇到下一个不同字符更新, 用pre保留cur值last=c// 保留当前字符串count+=min(pre,cur)// 比较前2个不同字符出现次数的最小值pre=cur// pre 保留前一个字符出现的次数cur=0// 如果不相等，cur 统计次数清零}cur++// 统计当前字符出现的次数i++// 本次循环次数+1}returncount}// 辅助函数：返回两个整数中较小的一个funcmin(a,bint)int{ifa<b{returna}returnb}

2 ）方案2

funccountBinarySubstrings(sstring)int{index:=0// 当前循环次数n:=len(s)// 字符串长度last:=0// 上一次统计数量ans:=0// 最终统计结果forindex<n{c:=s[index]// 获取当前字符count:=0// 重置每次统计的计数// 统计当前相同字符串的结果forindex<n&&s[index]==c{index++count++}ans+=min(count,last)// 从 count 和 last 找到最小的统计值，取最小值进行累加last=count// 缓存 count 统计值}returnans}// 辅助函数：返回两个整数中较小的一个funcmin(a,bint)int{ifa<b{returna}returnb}

Java 版算法实现

1 ) 暴力枚举与正则匹配法 (Brute Force with Regular Expression)

// 下面的正则算法超出时间限制！importjava.util.ArrayList;importjava.util.List;importjava.util.regex.Matcher;importjava.util.regex.Pattern;publicclassMain1{publicstaticintcountBinarySubstrings(Strings){List<String>r=newArrayList<>();for(inti=0;i<s.length()-1;i++){Stringsub=match(s.substring(i));if(!sub.isEmpty()){r.add(sub);}}returnr.size();}privatestaticStringmatch(Strings){Patternp=Pattern.compile("^(0+|1+)");Matcherm=p.matcher(s);if(!m.find()){return"";}Stringj=m.group(1);charc=j.charAt(0)=='0'?'1':'0';Stringo=String.valueOf(c).repeat(j.length());Patternreg=Pattern.compile("^("+j+o+")");Matcherm2=reg.matcher(s);if(m2.find()){returnm2.group(1);}return"";}publicstaticvoidmain(String[]args){System.out.println(countBinarySubstrings("00110011"));}}

算法说明

1. 遍历字符串的每个可能起点，通过substring截取后缀子串。
2. 使用正则表达式提取后缀开头的连续相同字符段（如000）及其长度。
3. 动态构造“等长且字符相反”的正则表达式（如^000111），验证并提取符合条件的子串。
4. 将所有匹配到的有效子串存入列表，最终返回列表的大小作为结果。

无法通过的 Case 解释

1. 正则表达式超限报错：当输入包含极长的连续相同字符（例如几千个'1'）时，动态拼接出的正则表达式长度会达到上万字符，超出 Java 正则引擎的处理限制，导致PatternSyntaxException或底层栈溢出。
2. 超时 (Time Limit Exceeded)：s.substring(i)每次都会创建新的字符串对象，结合正则表达式的编译与匹配，整体时间复杂度接近O(N2)O(N^2)O(N2)。对于长测试用例，执行时间会远超限制。
3. 内存溢出 (Memory Limit Exceeded)：代码将所有匹配到的子串字符串都保存到了ArrayList中。题目仅要求返回数量，这种存储方式会造成极大的额外空间开销。

2 ) 一次遍历与分组统计法 (Linear Scan and Group Counting)

publicclassMain2{publicstaticintcountBinarySubstrings(Strings){intcount=0;// 用于统计最终符合要求的长度charlast='_';// 上一个字符初始化intpre=0;// 上一次统计次数intcur=0;// 当前字符出现的统计次数inti=0;// 当前循环次数while(i<=s.length()){charc=i<s.length()?s.charAt(i):' ';// 获取当前字符，越界时赋空格// 第一次一定会执行，last 就会被重新赋值，last 保留的是前一个字符// 只有遇到新的值时，last 才会变成当前新值，这个if里面对当前字符 c 进行统计次数if(last!=c){// 遇到下一个不同字符更新，用pre保留cur值last=c;// 保留当前字符串count+=Math.min(pre,cur);// 比较前2个不同字符出现次数的最小值pre=cur;// pre 保留前一个字符出现的次数cur=0;// 如果不相等，cur 统计次数清零}cur++;// 统计当前字符出现的次数i++;// 本次循环次数+1}returncount;}publicstaticvoidmain(String[]args){System.out.println(countBinarySubstrings("00110011"));}}

算法说明

1. 状态初始化：使用pre记录前一组连续字符的长度，cur记录当前组连续字符的长度，count记录最终结果。
2. 线性扫描：遍历字符串，逐个字符判断。若当前字符与前一个字符相同，则当前组的连续长度cur加 1。
3. 分组切换：当遇到不同的字符（或到达字符串末尾触发边界条件）时，说明当前连续字符组结束。此时，符合条件的子串数量取决于相邻两组长度的较小值，即累加Math.min(pre, cur)到count中。
4. 状态更新：将pre更新为当前的cur，并将cur重置为 0，开始统计新一组连续字符的长度。
5. 返回结果：遍历结束后，直接返回累加的count。该算法时间复杂度为O(N)O(N)O(N)，空间复杂度为O(1)O(1)O(1)，完美避免了正则和字符串切片带来的性能问题。

3 ) 游程统计法 (Run-Length Encoding / Consecutive Segment Counting)

publicclassMain3{publicstaticintcountBinarySubstrings3(Strings){// index 是当前循环次数, n 是字符串长度, last是上一次统计数量, ans 是最终统计结果intindex=0,n=s.length(),last=0,ans=0;while(index<n){charc=s.charAt(index);// c 是当前字符串intcount=0;// 每次count都重置一下// 统计当前相同字符串的结果while(index<n&&s.charAt(index)==c){++index;++count;}ans+=Math.min(count,last);// 从 count 和 last 找到最小的统计，取最小值last=count;// 缓存 count统计}returnans;}publicstaticvoidmain(String[]args){System.out.println(countBinarySubstrings3("00110011"));}}

算法说明

1. 外层循环控制分组：使用index遍历字符串，每次获取当前字符c作为当前连续段的基准字符。
2. 内层循环统计长度：通过内层while循环，只要字符与c相同就继续向后遍历，累加当前连续字符的长度count，并同步推进index。
3. 计算有效子串：内层循环结束时，当前连续段统计完毕。将当前段长度count与上一段长度last取较小值，累加到最终结果ans中。
4. 状态传递：将当前段长度count赋值给last，作为下一段比较的基准，随后进入下一次外层循环处理新的字符段。
5. 该算法通过内层循环直接跳过相同字符，减少了外层循环的判断次数，时间复杂度为O(N)O(N)O(N)，空间复杂度为O(1)O(1)O(1)，逻辑非常清晰。