Skip to main content

696. Count Binary Substrings

easy

Count substrings with equal numbers of consecutive 0s and 1s, all 0s grouped together and all 1s grouped together. Group-length compression makes the answer one summation.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a binary string s, return the number of non-empty substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur.

Constraints

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

Examples

Example 1

Input
s = "00110011"
Output
6

Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.

Example 2

Input
s = "10101"
Output
4

Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Compress s into run-lengths: e.g. "00110011" -> [2, 2, 2, 2].

Hint 2

Adjacent runs of length a and b contribute min(a, b) valid substrings.

Hint 3

Sum min(groups[i-1], groups[i]) across all adjacent pairs.

Solution approach

Reveal approach

Compress the input into a list of run-lengths. For example, '00110011' becomes [2, 2, 2, 2]. A valid substring must straddle exactly one boundary between a 0-run and a 1-run (or vice versa) and pick equal counts from each side. That count is min(left_run, right_run). Sum min(groups[i-1], groups[i]) for i from 1 to len(groups) - 1. The streaming variant tracks prev_run and curr_run as scalars and adds min(prev_run, curr_run) whenever the digit changes — O(n) time, O(1) space, single pass.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming
  • two-pointers
  • string

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Helix

Practice these live with InterviewChamp.AI

Drill Count Binary Substrings and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →