Count Binary Substrings: The Group Counting Trick

LeetCode 696, Count Binary Substrings, asks you to count how many substrings of a binary string have an equal number of consecutive 0s and consecutive 1s, where all the 0s and all the 1s in the substring are grouped together. At first glance you might think about checking every possible substring, but there is a much cleaner O(n) approach hiding in the structure of the string.

The problem

Given a binary string s, count the number of non-empty substrings where the number of 0s equals the number of 1s, and every 0 and every 1 in the substring are grouped consecutively. For example, "0011" counts because there are two 0s followed by two 1s. But "0101" does not count because the 0s and 1s are not grouped together.

Example 1: s = "00110011" returns 6. The valid substrings are "0011", "01", "10", "1100", "10", "01" (some occur at different positions).

Example 2: s = "10101" returns 4. The valid substrings are "10", "01", "10", "01".

The approach

The key insight is that you do not need to examine every substring. Instead, think about the boundaries between groups of consecutive identical characters. Every valid substring straddles exactly one such boundary, with some number of characters from the group on the left and the same number from the group on the right.

Here is the plan:

1. Scan through the string and count the length of each consecutive group. For "00110011", the groups are [2, 2, 2, 2] (two 0s, two 1s, two 0s, two 1s).
2. For every pair of adjacent groups, the number of valid substrings at that boundary is min(left_group, right_group). If you have 3 zeros followed by 2 ones, you can form "01" and "0011" but not "000111" because there are not enough ones. That gives min(3, 2) = 2 valid substrings.
3. Sum up min(prev, curr) across all adjacent pairs and you have the answer.

You can simplify the implementation further by not storing all group sizes in an array. You only need the previous group count and the current group count as you scan. This keeps the space at O(1).

The code

def countBinarySubstrings(s):
    prev = 0
    curr = 1
    result = 0

    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            curr += 1
        else:
            result += min(prev, curr)
            prev = curr
            curr = 1

    result += min(prev, curr)
    return result

prev = 0 and curr = 1. You start with prev at 0 (no previous group yet) and curr at 1 (the first character forms a group of size 1).

if s[i] == s[i - 1]. If the current character matches the previous one, it extends the current group. You increment curr.

else. When the character changes, you have reached a boundary between two groups. The number of valid substrings at this boundary is min(prev, curr). You add that to result, then shift: prev takes the value of curr, and curr resets to 1 for the new group.

result += min(prev, curr). After the loop ends, you still need to account for the boundary between the last two groups, since the loop only processes boundaries when it encounters a character change. This final addition handles the last pair.

Complexity analysis

The two-variable approach is optimal. You make a single pass through the string, doing O(1) work per character. No auxiliary data structures are needed.

Building blocks

Group counting

Many string and array problems reduce to counting consecutive groups of identical elements. The pattern is always the same: maintain a counter for the current run, and when the element changes, process the completed group and reset. This exact technique shows up in String Compression (writing the count of each group), Count and Say (describing groups aloud), and many run-length encoding problems. Once you can write the group-counting loop from memory, you can snap it into any problem that depends on consecutive runs.

Edge cases

• All same characters. A string like "0000" has only one group. There are no adjacent pairs, so the answer is 0.
• Two characters. A string like "01" has two groups of size 1. min(1, 1) = 1, so the answer is 1.
• Alternating characters. A string like "010101" has groups [1, 1, 1, 1, 1, 1]. Each adjacent pair contributes min(1, 1) = 1, giving 5 valid substrings.
• Unequal group sizes. When adjacent groups differ in size, like "000111" vs "00011111", min(prev, curr) correctly limits the count to the smaller group.
• Single character. The string "0" has one group and no boundaries, so the answer is 0.

From understanding to recall

The group counting trick is one of those patterns that feels obvious once you see it but is easy to forget under pressure. The piece that slips away is the final result += min(prev, curr) after the loop. That line handles the last boundary, and forgetting it is the most common bug.

Practice writing this from scratch on a blank screen. The solution is short, just a few lines, but getting each detail right matters. Track whether you remember to initialize prev = 0 (not 1), whether you handle the post-loop addition, and whether you correctly reset curr = 1 at each boundary. Once you can write it without hesitation, space out your reviews and let spaced repetition lock it in.

Related posts

• String Compression - Uses the same group counting loop to compress consecutive characters in place
• Longest Substring Without Repeating - A sliding window approach to tracking character patterns in strings
• Longest Continuous Increasing Subsequence - Another single-pass problem that tracks consecutive runs with a counter