Given a binary string s, return the number of non-empty substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively.
Substrings that occur multiple times are counted the number of times they occur.
Example 1:
Input: s = "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.
Example 2:
Input: s = "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.
Constraints:
1 <= s.length <= 105s[i] is either '0' or '1'.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.
In this approach, we maintain two counters to track consecutive groups of 0's and 1's as we move through the string. By comparing these group counts, we can determine the number of valid equal-length substrings.
As we traverse the string, we increment the count for the current group and check if the previous group length is greater than or equal to the current group length. This indicates that we can form a valid substring.
The above code uses a two-pointer technique to track the lengths of consecutive characters. It keeps track of the current and previous group lengths and increases the output count based on the lesser of the two. This ensures only valid substrings with equal '0's and '1's are counted.
Time Complexity: O(n) because we make a single pass through the string.
Space Complexity: O(1) since we use a constant amount of extra space.
This approach involves creating an array to store the lengths of consecutive 0's and 1's. By iterating through this array, we add the minimum value of each pair to a count, which represents valid substrings.
First, traverse the string to form groups, then iterate through the formed group to compute the valid substring count based on consecutive groups' minimum lengths.
In this C implementation, after creating a dynamically sized array to store consecutive group lengths, we compute valid substrings by iterating over these lengths and summing the minimum values of consecutive pairs.
Time Complexity: O(n) - The string is traversed twice, but both passes are O(n).
Space Complexity: O(n) due to the need to store group lengths.
| Approach | Complexity |
|---|---|
| Two-Pointer Approach | Time Complexity: O(n) because we make a single pass through the string. |
| Group Count Array Approach | Time Complexity: O(n) - The string is traversed twice, but both passes are O(n). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Group Count Array | O(n) | O(n) | When first identifying the pattern of consecutive character groups |
| Two-Pointer Group Tracking | O(n) | O(1) | Best for interviews and optimal implementations with constant space |
Count Binary Substrings | Live Coding with Explanation | Leetcode - 696 • Algorithms Made Easy • 27,062 views views
Watch 9 more video solutions →Practice Count Binary Substrings with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor