Quick Overview

Count binary substrings with equal numbers of zeros and ones arranged in two consecutive blocks, including overlapping occurrences.

Count Binary Substrings with Two Equal Blocks

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

Given a binary string `s`, return the number of its nonempty contiguous substrings that contain an equal number of `0` characters and `1` characters, with all the `0` characters consecutive and all the `1` characters consecutive within the substring. A valid substring therefore has exactly two nonempty blocks: either a block of zeros followed by a block of ones, or a block of ones followed by a block of zeros. Count substrings at different positions separately, even when their text is identical. ### Input - `s`: a string containing only `0` and `1`. ### Output Return the number of valid substrings as an integer. ### Constraints and Edge Cases - For this practice version, `1 <= s.length <= 100000`. - A one-character string has no valid substrings. - A string containing only one kind of character has no valid substrings. - Substrings may overlap. - A substring such as `0101` is invalid: its counts are equal, but its characters are not arranged into exactly two blocks. ### Example 1 ```text s = "00110011" output = 6 ``` The valid occurrences are `0011` at positions `0..3` and `4..7`, `01` at `1..2` and `5..6`, `1100` at `2..5`, and `10` at `3..4`. Positions are zero-based and inclusive. ### Example 2 ```text s = "0101" output = 3 ``` The three length-two substrings qualify. The entire string does not.

Overview: Count binary substrings with equal numbers of zeros and ones arranged in two consecutive blocks, including overlapping occurrences.

Read the full Microsoft Software Engineer interview experience this question came from

Given a binary string `s`, return the number of its nonempty contiguous substrings that contain an equal number of `0` characters and `1` characters, with all the `0` characters consecutive and all the `1` characters consecutive within the substring. A valid substring therefore has exactly two nonempty blocks: either a block of zeros followed by a block of ones, or a block of ones followed by a block of zeros. Count substrings at different positions separately, even when their text is identical. ### Input - `s`: a string containing only `0` and `1`. ### Output Return the number of valid substrings as an integer. ### Constraints and Edge Cases - For this practice version, `1 <= s.length <= 100000`. - A one-character string has no valid substrings. - A string containing only one kind of character has no valid substrings. - Substrings may overlap. - A substring such as `0101` is invalid: its counts are equal, but its characters are not arranged into exactly two blocks. ### Example 1 ```text s = "00110011" output = 6 ``` The valid occurrences are `0011` at positions `0..3` and `4..7`, `01` at `1..2` and `5..6`, `1100` at `2..5`, and `10` at `3..4`. Positions are zero-based and inclusive. ### Example 2 ```text s = "0101" output = 3 ``` The three length-two substrings qualify. The entire string does not.

Constraints

  • 1 <= s.length <= 100000; every character is 0 or 1.
  • A valid occurrence has exactly two nonempty constant blocks of equal length, in either zero-then-one or one-then-zero order.
  • Count different positions separately, even for identical text; overlapping occurrences are allowed.
  • Return only the integer count. One-character and single-symbol strings return zero.

Examples

Input: ('00110011',)

Expected Output: 6

Explanation: Published sample 1: three run boundaries each contribute two occurrences.

Input: ('0101',)

Expected Output: 3

Explanation: Published sample 2: each of the three adjacent length-two occurrences qualifies.

Loading coding console...

Show the approach

Approach

Partition the string conceptually into maximal runs of equal characters. A valid substring crosses exactly one boundary between adjacent runs. If those runs have lengths p and q, choosing t characters from each side gives exactly one occurrence for each t from 1 through min(p,q). No other occurrence can cross that boundary while having two equal nonempty blocks.

Keep only the lengths of the previous completed run and the current run. Equal characters extend the current run. At a character change, add the contribution of the previous/current pair, then move the current length into the previous slot and start a new run of length one. After the scan, add the final pair's contribution. The initial previous length is zero, so the first transition contributes no nonexistent pair.

Every valid occurrence has one unique run boundary and a unique common block length, so summing min(p,q) over adjacent pairs counts it once. Substrings spanning more than two runs are never counted, while overlapping occurrences and repeated texts at different boundaries remain distinct.

The scan takes O(n) time and O(1) working space. The count is at most n-1: each adjacent-pair contribution is no larger than the length of its second run, and the first run contains at least one character. Therefore 32-bit counts are sufficient for n <= 100000. The C++ signature receives a string by value, which may additionally copy the input string; the counting algorithm itself stores only three integers.

Time complexity:
O(n) for one scan of the binary string.
Space complexity:
O(1) working space; the C++ by-value string parameter may additionally copy O(n) input storage.