EasyTwo PointersStringUpdated Sep 2026

696. Count Binary Substrings

Asked at DE Shaw, JPMorgan

Difficulty

Easy

Time

O(n)

Space

O(1)

Pattern

Two Pointers

Companies

2

Problem

You are given a string s made only of '0' and '1' characters. Count how many non-empty substrings of s satisfy two rules at the same time:

  1. The substring has the same number of 0s and 1s.
  2. Inside the substring, all the 0s are next to each other and all the 1s are next to each other. In other words, the substring looks like 000111 or 111000 — at most one switch between the two characters.

A substring is a contiguous piece of s. If the same piece of text appears in several places, each occurrence counts separately. Return the total count as an integer.

Valid pieces must be one block of 0s plus one block of 1s

svalid: 2 zeros + 2 ones0011001101234567"0011" has equal counts and each character forms one blocksinvalid: zeros split0011001101234567The full string fails rule 2, so it is not counted
In "00110011" the piece "0011" is valid, but the whole string is not, because its 0s are not grouped together.

Constraints

  • ●1 <= s.length <= 10^5
  • ●s[i] is either '0' or '1'

Examples

Example 1
Inputs = "00110011"
Output6
WhyThe valid pieces are "0011" (positions 0-3), "01" (1-2), "1100" (2-5), "10" (3-4), "0011" (4-7) and "01" (5-6). Each is one block of 0s followed by one block of 1s (or the reverse) with equal sizes. The whole string is not valid because its 0s are split into two groups.
Example 2
Inputs = "10101"
Output4
WhyOnly pairs of one 0 and one 1 work here, and there are four adjacent opposite pairs: "10", "01", "10", "01". Longer pieces would need a run of length 2, which this string does not have.

Asked At

2 companies
CompanyDifficulty
DE ShawEasyView all DE Shaw questions →
JPMorganEasyView all JPMorgan questions →

How to Think About It

1

Every valid substring sits across the boundary between two adjacent runs — a run of 0s followed by a run of 1s, or vice versa.

2

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).

3

So compress the string into run lengths and sum min(runs[i-1], runs[i]) over adjacent pairs.

4

You only need the previous and current run lengths, so it can be done in O(1) space.

5

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).

Count runs, then take min of neighbours

srun 2run 2run 2run 20011001101234567Step 1 — compress the string into run lengths: [2, 2, 2, 2]min(2,2) = 2min(2,2) = 2min(2,2) = 2total = 2 + 2 + 2 = 6count current runon a switch: add min(prev, cur)prev = cur, cur = 1after the loop add min(prev, cur)One pass keeps only the last two run lengths, so the extra space isconstant
Each boundary between two runs of different characters gives min(left run, right run) valid substrings.
ComplexityTime O(n)Space O(1)One pass over the string, keeping only the previous and current run lengths.

What Trips People Up in Real Interviews

1

Checking every substring for balance. That is O(n²) or worse; the run-length view is linear.

2

Forgetting the final min(prev, cur) after the loop, which drops the last pair of runs.

3

Counting substrings like "0101". The zeros and ones must each be consecutive.

4

Using max instead of min — only as many pairs as the shorter run can be formed.

Solution Code

O(n) time
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)

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

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 runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.