Count Binary Substrings(#696)
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
Input: 10101
Output: 4
🧠 Approach
Naive Approach
• Check all substrings and count 0s and 1s while verifying if 0s and 1s are grouped together.
• This results in O(n²) time complexity and is inefficient for large inputs.
• Optimized Approach
Instead of generating all substrings, we count consecutive 0s and 1s in groups.
• Walk through the string character by character.
• Count how many times the same character repeats in a row.
• Store each group count in an array.
• For every pair of adjacent groups, take the minimum of the two.
• Add all such minimums to get the final result.
This reduces the time complexity to O(n) and uses O(n) space.
💻 Code
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