#696

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Count Binary Substrings

Count Binary Substrings solves for the number of valid substrings with equal 0's and 1's, grouped consecutively in a binary string.

two pointers string

Problem Statement

Given a binary string s, return the number of non-empty substrings where the count of 0's equals the count of 1's, and both digits are grouped consecutively. Substrings that repeat should be counted each time they appear. For example, in s = "00110011", there are 6 such substrings.

The problem asks for counting substrings of equal 0's and 1's grouped together, but this excludes cases where 0's or 1's are scattered. Example input s = "10101" yields 4 valid substrings. The goal is to determine an efficient method for counting all such valid substrings.

Examples

Example 1

Input: s = "00110011"

Output: 6

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

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

Constraints

1 <= s.length <= 105
s[i] is either '0' or '1'.

Solution Approach

Two-pointer scanning with invariant tracking

The solution uses two pointers to traverse the binary string. As you move the pointers, track the number of consecutive 0's and 1's. The key is to maintain a valid balance between these groups and count substrings when their length conditions match. This avoids unnecessary recomputation.

Segment grouping

Group consecutive characters together to simplify the problem. This transforms the problem into finding equal-length groups of consecutive 1's and 0's. Each time a valid pair of adjacent groups is found, it contributes to the final count of valid substrings.

Efficient iteration and space optimization

Iterate through the binary string in linear time while keeping track of the previous segment's length. This ensures the space complexity remains constant and the algorithm operates in O(N) time, making it suitable for large strings up to the length of 105.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

The time complexity is O(N) because we only pass through the string once, while the space complexity is O(1) as we only use a constant amount of extra space for tracking lengths and counts.

What Interviewers Usually Probe

Look for an understanding of how to manage multiple groups of consecutive 1's and 0's efficiently.
Evaluate if the candidate can explain the trade-offs between time complexity and space optimization in this problem.
Check for the ability to reason about how to handle substrings that repeat in the final count.

Common Pitfalls or Variants

Common pitfalls

Failing to handle repeated substrings correctly – the solution should count each occurrence of valid substrings.
Incorrectly grouping consecutive characters, which may lead to missing valid substrings.
Not optimizing space by avoiding unnecessary data structures – the two-pointer approach should be used with careful tracking.

Follow-up variants

Consider if the input string includes alternating characters, like "010101".
What happens if the binary string has segments where the count of 0's or 1's exceeds the count of the other?
How would the solution adapt if we are asked to find the longest valid substring instead of counting them?

FAQ

How do I approach the 'Count Binary Substrings' problem?

Start by using the two-pointer scanning approach to identify consecutive 1's and 0's, then group them to count valid substrings.

What is the primary pattern used in 'Count Binary Substrings'?

The key pattern is two-pointer scanning with invariant tracking of consecutive groups of 1's and 0's.

How can I optimize space while solving 'Count Binary Substrings'?

Keep track of the previous segment's length without using extra data structures. This ensures O(1) space complexity.

What is the time complexity of 'Count Binary Substrings'?

The time complexity is O(N), where N is the length of the binary string, because the solution processes the string in one pass.

Are there any edge cases to consider for 'Count Binary Substrings'?

Yes, ensure to handle cases with strings where 0's and 1's alternate, or when one digit significantly exceeds the other in length.

terminal

Solution

Solution 1: Iteration and Counting

We can iterate through the string $s$, using a variable $\textit{pre}$ to record the count of the previous consecutive characters, and another variable $\textit{cur}$ to record the count of the current consecutive characters. The number of valid substrings ending with the current character is $\min(\textit{pre}, \textit{cur})$. We accumulate $\min(\textit{pre}, \textit{cur})$ to the answer, assign the value of $\textit{cur}$ to $\textit{pre}$, and continue iterating through string $s$ until the end.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        n = len(s)
        ans = i = 0
        pre = 0
        while i < n:
            j = i + 1
            while j < n and s[j] == s[i]:
                j += 1
            cur = j - i
            ans += min(pre, cur)
            pre = cur
            i = j
        return ans

Continue Practicing

#680 valid palindrome ii #647 palindromic substrings #763 partition labels