Count Binary Substrings

Count Binary Substrings

What is this problem about?

The Count Binary Substrings interview question asks you to count the number of non-empty substrings that have the same number of 0s and 1s, and all the 0s and all the 1s in these substrings are grouped consecutively. For example, 0011 is valid, but 0101 is not because the 0s and 1s are not grouped.

Why is this asked in interviews?

Companies like Meta, Amazon, and J.P. Morgan use the Two Pointers interview pattern for this problem because it’s a great test of pattern recognition. It’s an "Easy" difficulty problem that can be solved in O(N) time and O(1) space. It evaluates if you can simplify the problem from "checking every substring" to "counting adjacent blocks of characters."

Algorithmic pattern used

The primary pattern is Group Counting.

1. Count the lengths of consecutive groups of characters. For 001110, the groups are [2, 3, 1].
2. For any two adjacent groups of lengths A and B, the number of valid substrings you can form is min(A, B).
3. Sum these minimums for all adjacent group pairs.

Example explanation

String: 00110

1. Groups: 00 (length 2), 11 (length 2), 0 (length 1).
2. Group lengths: [2, 2, 1].
3. Pair 1 (2, 2): min(2, 2) = 2. (Substrings: 01, 0011)
4. Pair 2 (2, 1): min(2, 1) = 1. (Substrings: 10)
5. Total = 2 + 1 = 3.

Common mistakes candidates make

• O(N^2) search: Trying to check every possible substring, which is unnecessary and slow.
• Complex Logic: Over-complicating the condition "0s and 1s must be grouped."
• Space Usage: Creating an entire array to store group counts when you only need to keep track of the previous_group_count and current_group_count.

Interview preparation tip

This problem is all about "local properties." Whenever you see a requirement for "consecutive grouping," try to break the input into blocks and see how adjacent blocks interact.