Count Binary Substrings
(#696), Easy
Category: String, Two Pointer
Problem Statement
You’re given a binary string. Your task is to count the number of substrings that: - Have equal number of 0s and 1s, and - All the 0s and all the 1s must be grouped together. Note: Repeated substrings are counted each time they occur.
Examples
Input: 00110011
Output: 6
Explanation: Valid substrings are: 0011, 01, 1100, 10, 0011, 01. We care about both count and grouping.
Input: 10101
Output: 4
Explanation: Valid substrings are: 10, 01, 10, 01
Approach
Brute Force
- Generate all possible substrings of the binary string.
- For each substring, count the number of consecutive 0s and 1s.
- Check if the number of 0s and 1s are equal and grouped together (i.e., all 0s come first followed by all 1s, or vice versa).
- If valid, increment the result count.
- Return the total count of such valid substrings.
// ❌ Inefficient brute-force approach not implemented due to O(n^2) complexity.Optimized Using Group Counts
- Initialize a list `groups` to store counts of consecutive characters.
- Iterate through the string and count the length of consecutive 0s or 1s.
- Push each group count to the `groups` array.
- For every adjacent pair of groups, take the minimum of the two (because that’s the maximum number of valid substrings between them).
- Sum up all these minimums to get the final result.
- Return the result.
var countBinarySubstrings = function(s) {
let groups = [];
let count = 1;
for (let i = 1; i < s.length; i++) {
if (s[i] === s[i - 1]) {
count++;
} else {
groups.push(count);
count = 1;
}
}
groups.push(count);
let result = 0;
for (let i = 1; i < groups.length; i++) {
result += Math.min(groups[i - 1], groups[i]);
}
return result;
};Complexity
Time: O(n) – One pass to count group sizes, one pass to compute result
Space: O(n) – For storing the group sizes in an array