Count binary substrings with grouped equal zeros and ones

Given a string of 0s and 1s, count its non-empty substrings that have the same number of 0s and 1s, with all the 0s together and all the 1s together. Substrings at different positions count separately, even if they are equal.

Interface

Unless you agree on a different interface with the interviewer, assume:

• count_binary_substrings(s: str) -> int

Example

count_binary_substrings("00110011")  ->  6   # 0011, 01, 1100, 10, 0011, 01
count_binary_substrings("10101")     ->  4   # 10, 01, 10, 01
count_binary_substrings("000111")    ->  3   # 000111, 0011, 01

Constraints

• 1 <= len(s) <= 10^5, s contains only 0 and 1.

Clarifying questions

• Do overlapping and repeated substrings each count?
• Is "0101" valid as a whole? (No: its zeros are not together.)
• Can the string contain other characters?

What a strong answer covers

• Every valid substring sits on the boundary between two adjacent runs, taking j characters from the end of one run and j from the start of the next.
• So two adjacent runs of lengths a and b contribute min(a, b), and the answer is the sum over neighbouring runs.
• One pass keeping only the previous and current run lengths: O(n) time, O(1) space.
• Why the brute force over all substrings is O(n^2) or worse.
• Tests: a single character, one long run, alternating characters.

Follow-ups

• Return the substrings themselves, or their start indices.
• Count substrings with equal numbers of 0s and 1s without the grouping rule (prefix sums and a hash map).
• Extend to three symbols in three consecutive equal blocks.