Count Binary Substrings

CountingStringTwo Pointers

Write a function to count 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. The substrings that you count must have two distinct characters and must respect the grouping condition.

Example 1

Input

[
  "00110011"
]

Output

Explanation. There are 6 substrings with equal number of consecutive 1's and 0's: '0011', '01', '1100', '10', '0011', and '01'.

Example 2

Input

[
  "10101"
]

Output

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

Example 3

Input

[
  "000111"
]

Output

Explanation. There are 3 substrings with equal number of consecutive 1's and 0's: '000111', '0011', and '01'.

Follow-up: How would you optimize your solution if multiple queries for different strings are expected?

Constraints:

The input string will only consist of '0's and '1's.

Views: 2