FilesExpand file tree

 master

/

count-binary-substrings.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

42 lines (40 loc) · 1.34 KB

 master

/

count-binary-substrings.py

Copy path

Top

File metadata and controls

• Code
• Blame

42 lines (40 loc) · 1.34 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

34

35

36

37

38

39

40

41

42

# Time: O(n)

# Space: O(1)

# 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.

#

# Note:

# s.length will be between 1 and 50,000.

# s will only consist of "0" or "1" characters.

class Solution(object):

def countBinarySubstrings(self, s):

"""

:type s: str

:rtype: int

"""

result, prev, curr = 0, 0, 1

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

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

result += min(prev, curr)

prev, curr = curr, 1

else:

curr += 1

result += min(prev, curr)

return result