Skip to main content

696. Count Binary Substrings

easy

Count substrings with equal counts of consecutive 0s and 1s — grouped so all 0s come together and all 1s come together. The run-length trick: min(prev_run, curr_run).

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.

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

Split the string into runs: '00110011' becomes [2, 2, 2, 2] (two 0s, two 1s, two 0s, two 1s).

Hint 2

For two adjacent runs of length a and b, the number of grouped substrings they form is min(a, b).

Hint 3

Sum min(prev_run, curr_run) over each adjacent pair of runs.

Hint 4

You can do it without materializing the runs array — keep two counters prev and curr and update on each character flip.

Solution approach

Reveal approach

Single-pass run accounting. Maintain prev (length of the previous run of identical characters) starting at 0 and curr (length of the current run) starting at 1. Walk i from 1 to n - 1: if s[i] == s[i-1], increment curr. Otherwise, add min(prev, curr) to the answer (those are all the grouped substrings that bridge the boundary), set prev = curr, and reset curr = 1. After the loop, add the final min(prev, curr) to capture the last boundary. Return the total. O(n) time, O(1) space. The trick is recognizing that consecutive runs of length a and b in the form 0^a 1^b (or 1^a 0^b) yield exactly min(a, b) valid grouped substrings.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • 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 Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →