# leetcode 696. Counting binary substrings (python)

Given a string

s
, Count the number of non-empty (continuous) substrings with the same number of 0 and 1, and all 0s and all 1s in these substrings are combined.

Repeated substrings must be counted for the number of times they appear.

Example 1:

```Input: "00110011"
Output: 6
Explanation: There are 6 substrings with the same number of consecutive 1s and 0s: "0011", "01", "1100", "10", "0011" and "01".

Please note that some repeated substrings must be counted for the number of times they appear.

In addition, "00110011" is not a valid substring, because all 0s (and 1s) are not combined.
```

Example 2:

```Input: "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01", they have the same number of consecutive 1s and 0s.
```

note:

• s.length
Between 1 and 50,000.
• s
Contains only "0" or "1" characters.
```class Solution(object):
def countBinarySubstrings(self, s):
"""
:type s: str
:rtype: int
"""
#Using the map function to find the combined length of 0 and 1 that are cut apart
L = list(map(len, s.replace('01', '0 1').replace('10', '1 0').split('')))
#Because it is limited that only 0 and 1 can be next to each other, only adjacent ones can team up, using the zip function
res = sum(min(a,b) for a,b in zip(L, L[1:]))
return res```

Knowledge point 1: map() function

map() is a built-in higher-order function in Python. It receives a function f and a list, and by applying the function f to each element of the list in turn, a new list is obtained and returned.

Knowledge point 2: zip function

The prototype of the zip function is: zip([iterable, …])

The parameter iterable is an iterable object and can have multiple parameters. This function returns a list with tuples as elements, where the i-th tuple contains the i-th element of each parameter sequence. The length of the returned list is truncated to the length of the shortest parameter sequence. When there is only one sequence parameter, it returns a list of 1-tuples. When there are no parameters, it returns an empty list.

Method Two:

The method below is easy to understand, but it cannot be AC ​​(because the time limit is exceeded)

```class Solution:
def countBinarySubstrings(self, s):
"""
:type s: str
:rtype: int
"""
if(len(s)<2 or s.count('0')==len(s) or s.count('1')==len(s)):
return 0
s2='01'
s3='10'
out=0
while(s.count(s2) or s.count(s3)):
out+=s.count(s2)
s2='0'+s2+'1'
out+=s.count(s3)
s3='1'+s3+'0'
return out```

Reference : https://blog.csdn.net/weixin_40449300/article/details/83477896