665. Substrings of Grouped Zeros and Ones

Count the substrings that have the SAME number of zeros as ones, with all the zeros together and all the ones together. Substrings at different positions count separately, even when they look identical.

00110011 -> 6 0011, 01, 1100, 10, 0011, 01 10101 -> 4 10, 01, 10, 01 0011 -> 2 0011 and 01

## Every answer sits on one boundary

A qualifying substring is a block of one character followed by a block of the other, so it straddles exactly ONE place where the character changes.

So instead of scanning substrings, scan the BOUNDARIES. For a boundary with a run of length p on the left and q on the right, the substrings centred there are the ones taking k of each for k from 1 to min(p, q).

answer = sum over adjacent run pairs of min(run[i], run[i+1])

## Two pointers to find the runs

i = 0 while i < n: j = i while j < n and s[j] == s[i]: j += 1 record the run length j - i i = j

One cursor marks the run start and the other walks to its end, exactly as in problem 623. Once the runs are in hand the answer is one more pass.

## Why counting by boundary cannot double count

Each qualifying substring straddles one boundary and only one, because it contains exactly one change of character. So the boundaries partition the answers and summing over them is safe.

That is the same regrouping idea as problem 570, where each pair's path was counted once per edge: find the object that each answer belongs to exactly once, and count by that.

## Boundaries

A string of one repeated character has a single run and no boundary, so the answer is 0.

01 answers 1, the whole string.

## Overflow

With 200000 characters the count can reach about 10^5, which fits easily. The sum of run lengths is bounded by n, so nothing large arises.

## Cost

Time O(n). Space O(1) if the runs are consumed as they are found.

Constraints - `1 ≤ length ≤ 200000` - the string contains only `0` and `1`