696.count-binary-substrings.md

696. 计数二进制子串

1. 题意

   • 给定一个字符串 s，计算：具有相同数量0和1的非空(连续)子字符串的数量。
   • 注意两点：
     1. 子串合法性：子串中的所有0和所有1，必须连续地（consecutively）聚集在一起，不能被分隔开。
     2. 重复出现的子串，也要计数。
   • 比如：输入: "00110011"，输出: 6
     • 子串合法性：
       • “00110011”不是合法子串，因为所有的0（和1）没有聚集在一起。
     • 重复出现的子串，也计数了。
       • 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。

2. 思路：按字符分组

   • 将字符串s按照0和1的连续段分组，存在counts数组中。

     • 比如，s = 00111011，可以得到 counts={2,3,1,2}。

   • counts数组中，两个相邻的数字为u或者v。

     • 对应着 u个0 和 v个1，或者u个1和v个0。
     • 所以，一对相邻的数字对答案的贡献 min{u,v}，就是能组成的满足条件的子串数目。

   • 遍历所有相邻的数对，求它们的贡献总和，即可得到答案。

3. 实现

   • 字符分组

     class Solution {
     public:
         int countBinarySubstrings(string str) {
             vector<int>count={0};
             int c=1;
             for(int i=1; i<str.size(); i++){
                 if(str[i]==str[i-1]){
                     c++;                
                 }
                 else{
                     count.push_back(c);
                     c=1;
                 }
             }
             // 易错！写一个for，和写成两个while，区别在这里。
             count.push_back(c);
     
             int res = 0;
             for(int i=1; i<count.size(); i++){
                 res += min(count[i], count[i-1]);
             }
             return res;
         }
     };
     

   • 优化空间复杂度之后

     class Solution {
     public:
         int countBinarySubstrings(string str) {
             int count=1, pre_c=0;
             int res = 0;
             for(int i=1; i<str.size(); i++){
                 if(str[i]==str[i-1]){
                     count++;                
                 }
                 else{
                     res += min(count, pre_c);
                     pre_c = count;
                     count=1;
                 }
             }        
             res += min(count, pre_c);
     
             return res;
         }
     };