Count Binary Substrings - Video Solutions

Problem Overview: Given a binary string s, count the number of substrings where the number of consecutive 0s and 1s are equal and grouped together. Valid substrings look like 0011, 01, or 1100 where all 0s and 1s appear in contiguous blocks.

Approach 1: Group Count Array (O(n) time, O(n) space)

Scan the string and compress it into counts of consecutive characters. For example, "001110" becomes group lengths [2,3,1]. A valid substring always forms between two adjacent groups because it requires equal counts of consecutive 0s and 1s. For each adjacent pair, add min(group[i], group[i+1]) to the result. The idea works because the smaller group limits how many balanced substrings can form across the boundary. This approach is easy to reason about and useful when first understanding the pattern in the string.

Approach 2: Two-Pointer Group Tracking (O(n) time, O(1) space)

Instead of storing all groups, track only the previous and current group lengths while scanning the string once. Use a running counter for the current block of identical characters. When the character changes, shift current to previous and reset the counter. Each time you extend a group, check if previous >= current; if true, another valid substring exists. This works because every new character may extend a balanced boundary between two groups. The method uses constant space and fits naturally with a two pointers style linear scan.

Recommended for interviews: The two-pointer group tracking approach is what interviewers usually expect. It demonstrates recognition of the grouping pattern and reduces memory usage to O(1). Starting with the group-array idea shows you understand the core observation, then optimizing it to constant space highlights strong problem-solving skills and familiarity with efficient string traversal techniques.