Katkat
Back

Count Binary Substrings with Two Equal Blocks

MicrosoftSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

Tests string traversal, run-length grouping, and recognizing how adjacent homogeneous blocks contribute to valid balanced substrings.

Count Binary Substrings with Two Equal Blocks

Given a binary string s, return the number of non-empty substrings that have an equal number of '0's and '1's, where all the '0's and all the '1's in the substring are grouped consecutively into two distinct blocks.

Substrings that occur multiple times are counted each time they appear.

Function Signature

def count_binary_substrings(s: str) -> int:
    pass

Input

  • s: A string consisting only of characters '0' and '1'.

Output

  • An integer representing the total count of valid binary substrings.

Constraints

  • 1 <= len(s) <= 10^5
  • s[i] is either '0' or '1'

Examples

Example 1

Input: s = "00110011"
Output: 6
Explanation:
Valid substrings are:
- "0011" (starts at index 0)
- "01" (starts at index 1)
- "1100" (starts at index 2)
- "10" (starts at index 3)
- "0011" (starts at index 4)
- "01" (starts at index 5)
Note that "00110011" is not valid because the 0s and 1s are not grouped into just two blocks.

Example 2

Input: s = "10101"
Output: 4
Explanation:
The valid substrings are "10", "01", "10", and "01".

Edge Cases to Consider

  • Strings with only one distinct character (e.g., "0000" or "1"), where the answer should be 0.
  • Alternating characters (e.g., "010101"), where each adjacent pair forms a valid substring of length 2.
  • Large inputs up to 10^5 characters, requiring an O(n) time complexity and O(1) auxiliary space solution.

Hints

Hint 1

Consider grouping consecutive identical characters into runs of counts (e.g., '00110' becomes [2, 2, 1]).

Hint 2

Between two adjacent groups of characters of sizes `a` and `b`, how many balanced substrings can be centered across the boundary?

Hint 3

You do not need to store all group counts in an array; keeping track of just the previous group length and the current group length is sufficient for O(1) space.

Follow-up questions

  • How would your approach change if the string could contain three distinct characters ('0', '1', and '2'), and you needed three consecutive equal blocks?
  • Can you return the starting and ending indices of all valid substrings instead of just the count without exceeding O(n) space for the returned list?
  • How would you handle a streaming input where characters arrive one at a time and you need to maintain the running count?