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'.The key observation in #696 Count Binary Substrings is that valid substrings contain the same number of consecutive 0s and 1s, grouped together (for example, 0011 or 01). Instead of checking every possible substring, an efficient approach focuses on the lengths of consecutive character groups.
Traverse the string once and track the size of the current group of identical characters and the size of the previous group. Whenever the character changes, compare the sizes of these two groups. The number of valid binary substrings formed between them is limited by the smaller group size. By accumulating this value during traversal, you can count all valid substrings efficiently.
This strategy works because each valid substring must span exactly two adjacent groups of 0s and 1s. The approach uses a single pass through the string, achieving O(n) time complexity and O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Group Counting / Two-Pointer Style Traversal | O(n) | O(1) |
Algorithms Made Easy
Use these hints if you're stuck. Try solving on your own first.
How many valid binary substrings exist in "000111", and how many in "11100"? What about "00011100"?
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.
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.
1var countBinarySubstrings = function(s) {
2 let prev = 0, curr = 1, count = 0;
3 for (let i =
The JavaScript solution involves iterating through the input string to find transitions between '0's and '1's and their group counts. We calculate the possible valid substrings by accumulating the minimum of the consecutive counts.
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.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is a common interview question because it tests pattern recognition and efficient string traversal. Interviewers often expect candidates to avoid brute force and identify the group-counting optimization.
No complex data structure is required for this problem. Simple integer counters are enough to track the sizes of the current and previous groups of characters. This keeps the solution efficient and memory usage minimal.
Yes, the idea can be interpreted as a two-pointer or group-tracking technique. Instead of explicitly maintaining two pointers, you track consecutive character runs and compare their lengths to count valid substrings efficiently.
The optimal approach tracks the lengths of consecutive groups of 0s and 1s while scanning the string once. By comparing the size of the current group with the previous group, you can determine how many valid substrings can be formed. This results in an O(n) time and O(1) space solution.
Similarly in Java, this approach first creates a list to hold counts of groups of 0's and 1's, and then sums the minimal group counts of adjacent entries.