Count Binary Substrings
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.
Valid substrings always sit at the boundary between a group of one character and a group of the other. A group of three 0's followed by a group of two 1's ("00011") contains two valid substrings spanning that boundary: "01" and "0011". The count equals the minimum of the two group sizes, min(3, 2) = 2, and the same holds at every boundary between adjacent groups.
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: A string this long has roughly n^2 / 2 substrings, about 5 billion at the upper limit, so checking each one individually is too slow. The target is an O(n) solution.s[i]is either'0'or'1': With only two characters, every run of identical characters is followed by a run of the other character, so the string splits into alternating groups.
Approach 1: Brute Force
Intuition
Check every possible substring and count the ones that qualify. A valid substring is a block of one character followed by an equally sized block of the other, so the check verifies that the substring looks like "000...111..." or "111...000..." with equal halves. Equal counts of 0's and 1's force an even length, so only even-length substrings need checking.
One detail matters: a failed length does not rule out longer lengths from the same start. At i = 0 in "0011", length 2 gives "00" (invalid) while length 4 gives "0011" (valid). The inner loop has to try every even length rather than stopping at the first failure.
Algorithm
- Initialize
count = 0. - For each starting index
ifrom0ton - 1: - For each even length
lenwithi + len <= n: - Check that the first half is all one character and the second half is all the other character.
- If both checks pass, increment
count. - Return
count.
Example Walkthrough
Code
- Time Complexity: O(n^3) in the worst case. There are O(n^2) start-and-length pairs, and each validity check scans up to O(n) characters. Early exits shorten many checks but do not change the bound: in an all-zeros string the first-half check always scans the full half before the second-half check fails.
- Space Complexity: O(1). Only a few integer variables and no extra data structures.
The validity check rescans characters whose pattern is already fixed by the runs in the string. A group of five 0's followed by a group of three 1's produces exactly min(5, 3) = 3 valid substrings at that boundary, and that number comes from the two group sizes alone. The next approach computes the group sizes in one pass and sums the minimums of adjacent pairs.
Approach 2: Group Counting
Intuition
A binary string is a sequence of alternating groups: a run of 0's, then a run of 1's, then 0's again, and so on. For example, "00110011" has groups of sizes [2, 2, 2, 2].
A valid substring spans exactly two adjacent groups. If one group has size a and the next has size b, that boundary produces min(a, b) valid substrings: lengths 2, 4, 6, ... up to 2 * min(a, b), each taking the same number of characters from both sides of the boundary.
A valid substring contains exactly one switch between characters, and that switch point is a group boundary of s. A substring that takes k characters from the end of the left group and k characters from the start of the right group is valid for any k from 1 to min(a, b), and no other substring crossing that boundary is valid. Because each valid substring contains exactly one boundary, summing min(a, b) over all boundaries counts every valid substring exactly once.
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 runs in O(n) time but stores every group size, even though the summing loop only ever reads two adjacent entries at a time. Two variables, the previous group size and the current one, carry all the state the sum needs, which removes the array entirely.
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 currently being built). Every time the character changes, the current group becomes the previous group and a new current group starts at size 1.
At each character, if prevGroupSize >= currGroupSize, one more valid substring ends at this position, so increment the count.
This per-character check produces the same sum as Approach 2. Consider a boundary between a group of size a and a following group of size b. As the new group grows, currGroupSize takes the values 1, 2, ..., b, and the check prevGroupSize >= currGroupSize passes exactly while currGroupSize <= a. That is min(a, b) increments for this boundary, the same contribution the groups array gave.
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.