Count Binary Substrings — Solution in Python, Java & C++
Count Binary Substrings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Count Binary Substrings is an easy coding problem on strings and two pointers, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Strings, Two Pointers
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a binary string s, count the non-empty substrings that have the same number of 0s and 1s, with all the 0s and all the 1s grouped consecutively.
Substrings that occur multiple times are counted once per occurrence.
Example 1
Input: s = "00110011"
Output: 6
Explanation: The qualifying substrings are "0011", "01", "1100", "10", "0011" and "01".
Example 2
Input: s = "10101"
Output: 4
Example 3
Input: s = "000"
Output: 0
Constraints
1 <= s.length <= 40s[i] is '0' or '1'.
Hints for Count Binary Substrings
Hint 1
Only runs of equal characters matter — compress the string into a list of run lengths.
Hint 2
Each adjacent pair of runs contributes
min(previous, current)valid substrings.Hint 3
You can keep just the previous and current run lengths and never build the list at all.
How to solve Count Binary Substrings
Compress the string into run lengths; each adjacent pair of runs contributes min(prev, cur) valid substrings.
Approach
- Scan the string, collecting the length of each maximal run of equal characters.
- Sum
min(groups[k-1], groups[k])over consecutive pairs.
Why it works
A valid substring is 0^m 1^m or 1^m 0^m, which must be centred on a boundary between two runs and can extend m characters into each — at most the shorter run's length. Different boundaries give different substrings, so the sums add.
Complexity
- Time —
O(n) - Space —
O(n) for the run list (O(1) keeping just prev/cur)
Pitfalls
- Substrings are counted per occurrence, which the per-boundary sum does automatically.
Reference solution
Python
def countBinarySubstrings(s: str) -> int:
groups = []
i = 0
while i < len(s):
j = i
while j < len(s) and s[j] == s[i]:
j += 1
groups.append(j - i)
i = j
return sum(min(groups[k - 1], groups[k]) for k in range(1, len(groups)))Java
public static int countBinarySubstrings(String s) {
int prev = 0, cur = 0, total = 0;
for (int i = 0; i < s.length(); i++) {
if (i > 0 && s.charAt(i) != s.charAt(i - 1)) {
prev = cur;
cur = 1;
} else {
cur++;
}
if (prev >= cur) total++;
}
return total;
}C++
int countBinarySubstrings(string s) {
int prev = 0, cur = 0, total = 0;
for (int i = 0; i < (int) s.size(); i++) {
if (i > 0 && s[i] != s[i - 1]) {
prev = cur;
cur = 1;
} else {
cur++;
}
if (prev >= cur) total++;
}
return total;
}JavaScript
var countBinarySubstrings = function(s) {
const groups = [];
let i = 0;
while (i < s.length) {
let j = i;
while (j < s.length && s[j] === s[i]) j++;
groups.push(j - i);
i = j;
}
let total = 0;
for (let k = 1; k < groups.length; k++) {
total += Math.min(groups[k - 1], groups[k]);
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Two Pointers Technique