Count Binary Substrings with Two Equal Blocks

Given a binary string s, return the number of its nonempty contiguous substrings that contain an equal number of 0 characters and 1 characters, with all the 0 characters consecutive and all the 1 characters consecutive within the substring.

A valid substring therefore has exactly two nonempty blocks: either a block of zeros followed by a block of ones, or a block of ones followed by a block of zeros. Count substrings at different positions separately, even when their text is identical.

Input

• s: a string containing only 0 and 1.

Output

Return the number of valid substrings as an integer.

Constraints and Edge Cases

• For this practice version, 1 <= s.length <= 100000.
• A one-character string has no valid substrings.
• A string containing only one kind of character has no valid substrings.
• Substrings may overlap.
• A substring such as 0101 is invalid: its counts are equal, but its characters are not arranged into exactly two blocks.

Example 1

s = "00110011"
output = 6

The valid occurrences are 0011 at positions 0..3 and 4..7, 01 at 1..2 and 5..6, 1100 at 2..5, and 10 at 3..4. Positions are zero-based and inclusive.

Example 2

s = "0101"
output = 3

The three length-two substrings qualify. The entire string does not.

Count Binary Substrings with Two Equal Blocks

Approach

Partition the string conceptually into maximal runs of equal characters. A valid substring crosses exactly one boundary between adjacent runs. If those runs have lengths p and q, choosing t characters from each side gives exactly one occurrence for each t from 1 through min(p,q). No other occurrence can cross that boundary while having two equal nonempty blocks.

Keep only the lengths of the previous completed run and the current run. Equal characters extend the current run. At a character change, add the contribution of the previous/current pair, then move the current length into the previous slot and start a new run of length one. After the scan, add the final pair's contribution. The initial previous length is zero, so the first transition contributes no nonexistent pair.

Every valid occurrence has one unique run boundary and a unique common block length, so summing min(p,q) over adjacent pairs counts it once. Substrings spanning more than two runs are never counted, while overlapping occurrences and repeated texts at different boundaries remain distinct.

The scan takes O(n) time and O(1) working space. The count is at most n-1: each adjacent-pair contribution is no larger than the length of its second run, and the first run contains at least one character. Therefore 32-bit counts are sufficient for n <= 100000. The C++ signature receives a string by value, which may additionally copy the input string; the counting algorithm itself stores only three integers.

• Time complexity: O(n) for one scan of the binary string.
• Space complexity: O(1) working space; the C++ by-value string parameter may additionally copy O(n) input storage.