Count Binary Substrings
Last Updated: March 31, 2026
Understanding the Problem
We need to count substrings where all 0's are grouped together and all 1's are grouped together, and both groups have the same size. So "0011" counts (two 0's followed by two 1's), "01" counts, "10" counts, "1100" counts. But "0101" does not count because the 0's and 1's are interleaved, not grouped.
The key observation is that valid substrings always occur at the boundary between a group of one character and a group of the other. If you have a group of three 0's followed by a group of two 1's ("00011"), the valid substrings that span this boundary are "01" and "0011". That's 2 substrings, which is the minimum of the two group sizes (min(3, 2) = 2). This pattern holds for every adjacent pair of groups in the string.
So the problem reduces to: group consecutive identical characters, then for each pair of adjacent groups, add the minimum of their sizes to the answer.
Key Constraints:
1 <= s.length <= 10^5— With n up to 100,000, we need an O(n) or O(n log n) solution. An O(n^2) brute force that checks every substring will hit 10 billion operations in the worst case, which is too slow.s[i]is either'0'or'1'— This is a binary string. There are only two possible characters, so groups naturally alternate between 0-groups and 1-groups.
Approach 1: Brute Force
Intuition
The most direct approach: check every possible substring to see if it's valid. A valid substring has all its 0's grouped together, all its 1's grouped together, and equal counts of both.
For any substring, we can check validity by verifying it looks like "000...111..." or "111...000..." with equal halves. Since valid substrings always have even length (equal 0's and 1's), we only need to check even-length substrings.
Algorithm
- Initialize
count = 0. - For each starting index
ifrom0ton - 1: - For each even length
lenfrom2ton - i: - Check if the first half is all one character and the second half is all the other character.
- If valid, increment
count. Otherwise, break (longer substrings from here won't be valid either). - Return
count.
Example Walkthrough
Code
- Time Complexity: O(n^2). For each starting index, we check substrings of increasing length. In the worst case (like "000...111..."), the inner loop runs O(n) times for O(n) starting positions.
- Space Complexity: O(1). Only a few integer variables and no extra data structures.
If we know there's a group of five 0's followed by three 1's, that tells us there are 3 valid substrings at that boundary. We don't need to check each one by scanning characters.
What if we counted the size of each consecutive group and used adjacent group sizes to compute the answer directly?
Approach 2: Group Counting
Intuition
Instead of checking every substring, let's think about the structure of the string differently. A binary string is just a sequence of groups: a run of 0's, then a run of 1's, then a run of 0's, and so on. For example, "00110011" has groups of sizes [2, 2, 2, 2].
Valid substrings always span exactly two adjacent groups. If one group has size a and the next has size b, the number of valid substrings crossing that boundary is min(a, b). You can form substrings of length 2, 4, 6, ... up to 2 * min(a, b) by taking equal portions from each group.
Every valid substring must look like 0...01...1 or 1...10...0, with equal counts. Such a substring always spans exactly two adjacent groups of different characters. If the left group has a characters and the right group has b characters, you can form valid substrings of length 2, 4, 6, ..., up to 2 * min(a, b). That gives exactly min(a, b) valid substrings per boundary.
Since every valid substring in the entire string must cross exactly one group boundary, and we account for every boundary exactly once, summing min(a, b) across all boundaries gives the total count with no double-counting and no misses.
Algorithm
- Walk through the string and compute the sizes of consecutive groups. Store them in an array.
- For each pair of adjacent groups, add
min(groups[i], groups[i+1])to the result. - Return the result.
Example Walkthrough
Code
- Time Complexity: O(n). We scan through the string once to build the groups array, then iterate through the groups array once. Both passes are O(n) total.
- Space Complexity: O(n). The groups array can have up to n entries in the worst case (alternating characters like "010101").
This approach is O(n) time but uses O(n) extra space. We only ever compare two adjacent groups at a time, so storing all groups is unnecessary.
What if we tracked just two values, the previous and current group sizes, and accumulated the result on the fly?
Approach 3: Optimized Single Pass (Two Counters)
Intuition
We can compress Approach 2 into a single pass without storing all group sizes. Maintain two variables: prevGroupSize (the size of the previous group) and currGroupSize (the size of the group we're currently building). Every time we transition from one character to another, the current group becomes the previous group, and we start a new current group.
At each character, if prevGroupSize >= currGroupSize, we can form one more valid substring at this boundary, so we increment the count.
Algorithm
- Initialize
prevGroupSize = 0,currGroupSize = 1, andcount = 0. - Iterate from index
1ton - 1: - If
s[i] == s[i - 1], the current group extends: incrementcurrGroupSize. - Otherwise, a new group starts: set
prevGroupSize = currGroupSizeand resetcurrGroupSize = 1. - If
prevGroupSize >= currGroupSize, incrementcount. - Return
count.
Example Walkthrough
Code
- Time Complexity: O(n). Single pass through the string. Each character is visited exactly once, with O(1) work per character.
- Space Complexity: O(1). Only three integer variables. No arrays, no hash maps, no extra data structures.