FilesExpand file tree

 master

/

count_binary_substring.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

33 lines (29 loc) · 1.15 KB

 master

/

count_binary_substring.py

Copy path

Top

File metadata and controls

• Code
• Blame

33 lines (29 loc) · 1.15 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

"""

Give a string s, count the number of non-empty (contiguous) 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: "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: "10101"

Output: 4

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

Reference: https://leetcode.com/problems/count-binary-substrings/description/

"""

def count_binary_substring(s):

cur = 1

pre = 0

count = 0

for i in range(1, len(s)):

if s[i] != s[i - 1]:

count = count + min(pre, cur)

pre = cur

cur = 1

else:

cur = cur + 1

count = count + min(pre, cur)

return count