Count Binary Substrings

Difficulty: Easy | Acceptance: 70.40% | Paid: No Topics: Two Pointers, String

Give 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.

Examples
Constraints
Brute Force
Group Counting
Two Pointers

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".

Constraints

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

Brute Force

Intuition We can check every possible substring to see if it meets the criteria: equal number of 0s and 1s, and all characters are grouped together.

Steps

Iterate through all possible starting indices of the substring.
For each starting index, expand the substring to the right one character at a time.
Keep track of the count of 0s and 1s in the current substring.
If the counts are equal and the substring has only one transition between 0 and 1 (e.g., 000111), increment the result.
Optimization: If the counts differ by more than the remaining characters, we can break early.

python

class Solution:
    def countBinarySubstrings(self, s: str) -&gt; int:
        n = len(s)
        count = 0
        for i in range(n):
            zeros = 0
            ones = 0
            for j in range(i, n):
                if s[j] == '0':
                    zeros += 1
                else:
                    ones += 1
                
                # If counts differ by more than 1, we can't form a valid substring starting at i ending at j or later
                # because adding more chars will only increase the difference.
                # However, we must be careful. A valid substring requires zeros == ones.
                # If abs(zeros - ones) &gt; (n - 1 - j), we can break, but simple check is just zeros == ones.
                
                if zeros == ones:
                    # Check if grouped: only one transition allowed
                    # A substring with equal 0s and 1s and grouped chars looks like 0...01...1 or 1...10...0
                    # This means there should be exactly one index k where s[k] != s[k+1] within the substring
                    transitions = 0
                    for k in range(i, j):
                        if s[k] != s[k+1]:
                            transitions += 1
                    if transitions == 1:
                        count += 1
        return count

Complexity

Time: O(n³) - Nested loops for substring generation and an inner loop to check transitions.
Space: O(1) - Only using a few variables.
Notes: This approach is too slow for the upper constraint limits but illustrates the problem logic clearly.

Group Counting

Intuition We can group consecutive identical characters. For example, 001110011 becomes groups of lengths [2, 3, 2, 2]. Valid substrings are formed at the boundary between two groups. The number of valid substrings between group i and i+1 is the minimum of their sizes.

Steps

Iterate through the string and count the lengths of consecutive groups of 0s and 1s. Store these lengths in an array.
Iterate through the array of group lengths.
For each pair of adjacent groups, add the minimum of the two lengths to the result.

python

class Solution:
    def countBinarySubstrings(self, s: str) -&gt; int:
        groups = []
        count = 1
        for i in range(1, len(s)):
            if s[i] == s[i-1]:
                count += 1
            else:
                groups.append(count)
                count = 1
        groups.append(count) # Append the last group
        
        ans = 0
        for i in range(len(groups) - 1):
            ans += min(groups[i], groups[i+1])
        return ans

Complexity

Time: O(n) - We traverse the string twice (once to group, once to sum).
Space: O(n) - We store the group counts in an array.
Notes: This is a very intuitive approach that simplifies the problem by aggregating data.

Two Pointers

Intuition We don’t actually need to store all the group counts. We only need the length of the previous group and the length of the current group. As we iterate, we can update these values and calculate the contribution to the result immediately.

Steps

Initialize prev (previous group length) to 0 and curr (current group length) to 1.
Iterate through the string starting from the second character.
If the current character is the same as the previous one, increment curr.
If it changes, the current group ends. The number of valid substrings ending at this boundary is min(prev, curr). Add this to the result. Then, set prev = curr and reset curr = 1.
After the loop, add min(prev, curr) one last time to account for the final boundary.

python

class Solution:
    def countBinarySubstrings(self, s: str) -&gt; int:
        prev = 0
        curr = 1
        ans = 0
        for i in range(1, len(s)):
            if s[i] == s[i-1]:
                curr += 1
            else:
                ans += min(prev, curr)
                prev = curr
                curr = 1
        ans += min(prev, curr)
        return ans

Complexity

Time: O(n) - Single pass through the string.
Space: O(1) - Only using a few integer variables.
Notes: This is the optimal solution, minimizing both time and space complexity.