###### tags: `Leetcode` `easy` `string` `python` `c++`

# 696. Count Binary Substrings

## 題目:
Given a binary string ```s```, return the number of non-empty substrings that have the same number of ```0```'s and ```1```'s, and all the ```0```'s and all the ```1```'s in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

**Example 1:**

Input: s = "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".
Notice that some of these substrings repeat and are counted the number of times they occur.
Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.

**Example 2:**

Input: s = "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

## 解題想法:
* 題目為，找滿足連續子字符串中**01連續個數相等**的子字符串的個數

ex: s="0010001100"
stack=[2,1,3,2,2]
子字串為01交錯而成，長度為min(a,b)
所以子字串個數: 
min(2,1)=1
min(1,3)=1
min(3,2)=2
min(2,2)=2
res=1+1+2+2=6

why: min(3,2)=2個子字串
即為: (01,0011)兩個

## Python:

class Solution(object):
    def countBinarySubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        curLen=1
        stack=[]
        res=0
        for i in range(1,len(s)):
            if s[i]==s[i-1]:
                curLen+=1
            else:
                stack.append(curLen)
                curLen=1
        stack.append(curLen)
        for i in range(1,len(stack)):
            res+=min(stack[i],stack[i-1])
        return res

if __name__=='__main__':
    result=Solution()
    ans=result.countBinarySubstrings(s="0010001100")
    print(ans)

## C++:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int countBinarySubstrings(string s) {
        int curLen=1;
        vector<int> subLen;
        int res=0;
        for (int i=1; i<s.size(); i++){
            if (s[i]==s[i-1])
                curLen+=1;
            else{
                subLen.push_back(curLen);
                curLen=1;
            }
        }
        subLen.push_back(curLen);
        for (int i=1; i<subLen.size(); i++){
            res+=min(subLen[i],subLen[i-1]);
        }
        return res;
    }
};

int main(){
    string s="0010001100";
    Solution res;
    int ans=res.countBinarySubstrings(s);
    cout<<ans<<endl;
    return 0;
}