Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A valid substring crosses exactly one boundary between a run of zeros and a run of ones. If the adjacent run lengths are a and b, we can take one character from each side, then two, up to min(a, b). Those are all valid substrings at that boundary, with no overlap in how they are counted.

Approach

Scan the string into lengths of consecutive equal-character runs. The reference code also creates an initial zero-length sentinel, which contributes nothing.
For every neighboring pair of run lengths, add their minimum to the result.
Return the sum. Longer substrings spanning another run boundary are excluded because their zeros or ones would no longer form a single consecutive group.

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        n = len(s)
        arr = []
        last = -1
        cnt = 0

        for c in s:
            if c == last:
                cnt += 1
            else:
                arr.append(cnt)
                last = c
                cnt = 1

        if cnt:
            arr.append(cnt)

        res = 0

        for i in range(1, len(arr)):
            res += min(arr[i], arr[i - 1])

        return res

Complexity analysis

For a string of length n, forming run lengths and comparing adjacent runs takes O(n) time. The run-length array uses O(n) auxiliary space in the worst case.