Count Binary Substrings - Solution & Explanation
Problem Statement
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'.
Approach Overview
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.
Approach 1: Two-Pointer Approach
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.
Complexity
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.
Approach 2: Group Count Array Approach
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.
Complexity
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 3: Iteration and Counting
We can iterate through the string s, using a variable pre to record the count of the previous consecutive characters, and another variable cur to record the count of the current consecutive characters. The number of valid substrings ending with the current character is min(pre, cur). We accumulate min(pre, cur) to the answer, assign the value of cur to pre, and continue iterating through string s until the end.
The time complexity is O(n), where n is the length of string s. The space complexity is O(1).
Complexity Comparison
| 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). |
| Iteration and Counting | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Count Binary Substrings | Live Coding with Explanation | Leetcode - 696 • Algorithms Made Easy • 27,396 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Binary Substrings easy or hard?
How to solve Count Binary Substrings in O(n)?
What is the best approach for Count Binary Substrings?
What data structure is used in Count Binary Substrings?
What is the time complexity of Count Binary Substrings?
Count Binary Substrings Python or Java solution approach?
Is Count Binary Substrings asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Count Binary Substrings with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor