Count Binary Substrings
Asked at DE Shaw, JPMorgan
Problem
Count Binary Substrings asks how many non-empty substrings have equal numbers of 0s and 1s with all the 0s grouped together and all the 1s grouped together, such as "0011" or "10". Counting substrings directly is slow; thinking in runs of equal characters makes it a one-line formula.
Asked At
| Company | Difficulty | |
|---|---|---|
| DE Shaw | Easy | View all DE Shaw questions → |
| JPMorgan | Easy | View all JPMorgan questions → |
How to Think About It
Every valid substring sits across the boundary between two adjacent runs — a run of 0s followed by a run of 1s, or vice versa.
Key insight: if two adjacent runs have lengths a and b, they contribute exactly min(a, b) valid substrings ("01", "0011", "000111", ... up to the shorter run).
So compress the string into run lengths and sum min(runs[i-1], runs[i]) over adjacent pairs.
You only need the previous and current run lengths, so it can be done in O(1) space.
Walkthrough for "00110011": runs [2,2,2,2] -> 2 + 2 + 2 = 6.
Optimal Approach
Step 1: prev = 0, cur = 1, total = 0.
Step 2: For i from 1 to n-1:
If s[i] == s[i-1]: cur += 1.
Else: total += min(prev, cur); prev = cur; cur = 1.
Step 3: total += min(prev, cur) for the final pair of runs.
Step 4: Return total.
Time: O(n). Space: O(1).
What Trips People Up in Real Interviews
Checking every substring for balance. That is O(n²) or worse; the run-length view is linear.
Forgetting the final min(prev, cur) after the loop, which drops the last pair of runs.
Counting substrings like "0101". The zeros and ones must each be consecutive.
Using max instead of min — only as many pairs as the shorter run can be formed.
Solution Code
def countBinarySubstrings(s):
prev, cur, total = 0, 1, 0
for i in range(1, len(s)):
if s[i] == s[i - 1]:
cur += 1
else:
total += min(prev, cur)
prev, cur = cur, 1
return total + min(prev, cur)Frequently Asked Questions
What is the Count Binary Substrings problem?
Count Binary Substrings asks how many non-empty substrings have equal numbers of 0s and 1s with all the 0s grouped together and all the 1s grouped together, such as `"0011"` or `"10"`. Counting substrings directly is slow; thinking in runs of equal characters makes it a one-line formula.
How do you solve Count Binary Substrings?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Count Binary Substrings?
Count Binary Substrings is asked at DE Shaw, JPMorgan. It is a easy difficulty problem.
What are common mistakes on Count Binary Substrings?
- Checking every substring for balance. That is `O(n²)` or worse; the run-length view is linear.
- Forgetting the final `min(prev, cur)` after the loop, which drops the last pair of runs.
- Counting substrings like `"0101"`. The zeros and ones must each be consecutive.
- Using `max` instead of `min` — only as many pairs as the shorter run can be formed.