696. Count Binary Substrings - Solution

The problem

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

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.
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
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

Constraints:

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

Approach overview

Problem Overview: Given a binary string s, count the number of substrings where the number of consecutive 0s and 1s are equal and grouped together. Valid substrings look like 0011, 01, or 1100 where all 0s and 1s appear in contiguous blocks.

Approach 1: Group Count Array (O(n) time, O(n) space)

Scan the string and compress it into counts of consecutive characters. For example, "001110" becomes group lengths [2,3,1]. A valid substring always forms between two adjacent groups because it requires equal counts of consecutive 0s and 1s. For each adjacent pair, add min(group[i], group[i+1]) to the result. The idea works because the smaller group limits how many balanced substrings can form across the boundary. This approach is easy to reason about and useful when first understanding the pattern in the string.

Approach 2: Two-Pointer Group Tracking (O(n) time, O(1) space)

Instead of storing all groups, track only the previous and current group lengths while scanning the string once. Use a running counter for the current block of identical characters. When the character changes, shift current to previous and reset the counter. Each time you extend a group, check if previous >= current; if true, another valid substring exists. This works because every new character may extend a balanced boundary between two groups. The method uses constant space and fits naturally with a two pointers style linear scan.

Recommended for interviews: The two-pointer group tracking approach is what interviewers usually expect. It demonstrates recognition of the grouping pattern and reduces memory usage to O(1). Starting with the group-array idea shows you understand the core observation, then optimizing it to constant space highlights strong problem-solving skills and familiarity with efficient string traversal techniques.

Approach 1: Two-Pointer Approach

In this approach, we maintain two counters to track consecutive groups of 0's and 1's as we move through the string. By comparing these group counts, we can determine the number of valid equal-length substrings.

As we traverse the string, we increment the count for the current group and check if the previous group length is greater than or equal to the current group length. This indicates that we can form a valid substring.

Python

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

if __name__ == '__main__':
    sol = Solution()
    print(sol.countBinarySubstrings("00110011"))

Java

public class Solution {
    public int countBinarySubstrings(String s) {
        int prev = 0, curr = 1, count = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                curr++;
            } else {
                count += Math.min(prev, curr);
                prev = curr;
                curr = 1;
            }
        }
        return count + Math.min(prev, curr);
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countBinarySubstrings("00110011"));
    }
}

C++

#include <iostream>
#include <string>
using namespace std;

int countBinarySubstrings(string s) {
    int prev = 0, curr = 1, count = 0;
    for (size_t i = 1; i < s.size(); ++i) {
        if (s[i] == s[i - 1]) {
            ++curr;
        } else {
            count += min(prev, curr);
            prev = curr;
            curr = 1;
        }
    }
    return count + min(prev, curr);
}

int main() {
    string s = "00110011";
    cout << countBinarySubstrings(s) << endl;
    return 0;
}

JavaScript

var countBinarySubstrings = function(s) {
    let prev = 0, curr = 1, count = 0;
    for (let i = 1; i < s.length; i++) {
        if (s[i] === s[i - 1]) {
            curr++;
        } else {
            count += Math.min(prev, curr);
            prev = curr;
            curr = 1;
        }
    }
    return count + Math.min(prev, curr);
};

console.log(countBinarySubstrings("00110011"));

#include <stdio.h>
#include <string.h>

int countBinarySubstrings(char * s) {
    int prev = 0, curr = 1, count = 0;
    for (int i = 1; s[i] != '\0'; i++) {
        if (s[i] == s[i - 1]) {
            curr++;
        } else {
            count += (prev < curr) ? prev : curr;
            prev = curr;
            curr = 1;
        }
    }
    return count + ((prev < curr) ? prev : curr);
}

int main() {
    char s[] = "00110011";
    printf("%d\n", countBinarySubstrings(s));
    return 0;
}

using System;

public class Solution {
    public int CountBinarySubstrings(string s) {
        int prev = 0, curr = 1, count = 0;
        for (int i = 1; i < s.Length; i++) {
            if (s[i] == s[i - 1]) {
                curr++;
            } else {
                count += Math.Min(prev, curr);
                prev = curr;
                curr = 1;
            }
        }
        return count + Math.Min(prev, curr);
    }
    public static void Main(string[] args) {
        Solution sol = new Solution();
        Console.WriteLine(sol.CountBinarySubstrings("00110011"));
    }
}

The implementation in Python makes use of similar logic. The countBinarySubstrings method tracks the sizes of consecutive character blocks and calculates the valid substrings based on these block sizes.

Complexity

Time Complexity: O(n) due to a single iteration over the string.
Space Complexity: O(1) because we require constant additional space.

Try this approach in the editor

Approach 2: Group Count Array Approach

This approach involves creating an array to store the lengths of consecutive 0's and 1's. By iterating through this array, we add the minimum value of each pair to a count, which represents valid substrings.

First, traverse the string to form groups, then iterate through the formed group to compute the valid substring count based on consecutive groups' minimum lengths.

Python

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        groups = []
        count = 0
        i = 0
        n = len(s)
        while i < n:
            ch = s[i]
            count_ch = 0
            while i < n and s[i] == ch:
                i += 1
                count_ch += 1
            groups.append(count_ch)

        for j in range(1, len(groups)):
            count += min(groups[j - 1], groups[j])
        return count

if __name__ == '__main__':
    sol = Solution()
    print(sol.countBinarySubstrings('00110011'))

Java

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int countBinarySubstrings(String s) {
        List<Integer> groups = new ArrayList<>();
        int count = 0, n = s.length();
        int i = 0;

        while (i < n) {
            char ch = s.charAt(i);
            int c = 0;
            while (i < n && s.charAt(i) == ch) {
                i++;
                c++;
            }
            groups.add(c);
        }

        for (int j = 1; j < groups.size(); ++j) {
            count += Math.min(groups.get(j - 1), groups.get(j));
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countBinarySubstrings("00110011"));
    }
}

C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int countBinarySubstrings(string s) {
    vector<int> groups;
    int count = 0, n = s.length();
    int i = 0;
    while (i < n) {
        int c = 0;
        char ch = s[i];
        while (i < n && s[i] == ch) {
            i++;
            c++;
        }
        groups.push_back(c);
    }

    for (size_t j = 1; j < groups.size(); ++j) {
        count += min(groups[j-1], groups[j]);
    }
    return count;
}

int main() {
    string s = "00110011";
    cout << countBinarySubstrings(s) << endl;
    return 0;
}

JavaScript

var countBinarySubstrings = function(s) {
    let groups = [];
    let count = 0;
    let i = 0;
    let n = s.length;
    while (i < n) {
        let ch = s[i];
        let c = 0;
        while (i < n && s[i] === ch) {
            i++;
            c++;
        }
        groups.push(c);
    }

    for (let j = 1; j < groups.length; j++) {
        count += Math.min(groups[j - 1], groups[j]);
    }
    return count;
};

console.log(countBinarySubstrings("00110011"));

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int countBinarySubstrings(char * s) {
    int len = strlen(s);
    int *groups = (int *)malloc(len * sizeof(int));
    int groupIndex = 0, count = 0;
    groups[0] = 1;
    
    for (int i = 1; i < len; i++) {
        if (s[i] != s[i-1]) {
            groupIndex++;
            groups[groupIndex] = 1;
        } else {
            groups[groupIndex]++;
        }
    }
    
    for (int i = 1; i <= groupIndex; i++) {
        count += groups[i-1] < groups[i] ? groups[i-1] : groups[i];
    }

    free(groups);
    return count;
}

int main() {
    char s[] = "00110011";
    printf("%d\n", countBinarySubstrings(s));
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int CountBinarySubstrings(string s) {
        List<int> groups = new List<int>();
        int count = 0, n = s.Length;
        int i = 0;
        while (i < n) {
            char ch = s[i];
            int c = 0;
            while (i < n && s[i] == ch) {
                i++;
                c++;
            }
            groups.Add(c);
        }

        for (int j = 1; j < groups.Count; j++) {
            count += Math.Min(groups[j-1], groups[j]);
        }
        return count;
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        Console.WriteLine(sol.CountBinarySubstrings("00110011"));
    }
}

This Python implementation uses a similar method by first creating a list to store length of consecutive groups of similar digits, and then adds up the smaller counts of each consecutive pair in the list.

Complexity

Time Complexity: O(n), owing to traversing the string twice.
Space Complexity: O(n) for the list that stores lengths of each group.

Try this approach in the editor

Approach 3: Iteration and Counting

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

The time complexity is O(n), where n is the length of string s. The space complexity is O(1).

TypeScript

function countBinarySubstrings(s: string): number {
    const n = s.length;
    let ans = 0;
    let i = 0;
    let pre = 0;

    while (i < n) {
        let j = i + 1;
        while (j < n && s[j] === s[i]) {
            j++;
        }
        const cur = j - i;
        ans += Math.min(pre, cur);
        pre = cur;
        i = j;
    }

    return ans;
}

func countBinarySubstrings(s string) (ans int) {
	n := len(s)
	i := 0
	pre := 0
	for i < n {
		j := i + 1
		for j < n && s[j] == s[i] {
			j++
		}
		cur := j - i
		ans += min(pre, cur)
		pre = cur
		i = j
	}
	return
}

Rust

impl Solution {
    pub fn count_binary_substrings(s: String) -> i32 {
        let bytes = s.as_bytes();
        let n: usize = bytes.len();

        let mut ans: i32 = 0;
        let mut i: usize = 0;
        let mut pre: i32 = 0;

        while i < n {
            let mut j: usize = i + 1;
            while j < n && bytes[j] == bytes[i] {
                j += 1;
            }
            let cur: i32 = (j - i) as i32;
            ans += pre.min(cur);
            pre = cur;
            i = j;
        }

        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Two-Pointer Approach	Time Complexity: O(n) due to a single iteration over the string. Space Complexity: O(1) because we require constant additional space.
Group Count Array Approach	Time Complexity: O(n), owing to traversing the string twice. Space Complexity: O(n) for the list that stores lengths of each group.
Iteration and Counting	–

Complexity analysis

Approach	Time	Space	When to Use
Group Count Array	O(n)	O(n)	When first identifying the pattern of consecutive character groups
Two-Pointer Group Tracking	O(n)	O(1)	Best for interviews and optimal implementations with constant space

Frequently asked questions

Is Count Binary Substrings easy or hard?

Count Binary Substrings is classified as an Easy problem on LeetCode with an acceptance rate above 70%. The challenge lies in recognizing that valid substrings occur only between adjacent groups of consecutive 0s and 1s, which leads to an efficient linear-time solution.

How to solve Count Binary Substrings in O(n)?

Traverse the string while counting lengths of consecutive characters. Maintain two values: the length of the previous group and the current group. Each time the current group length becomes less than or equal to the previous group, increment the answer. This guarantees all valid balanced substrings are counted in one linear pass.

What is the best approach for Count Binary Substrings?

The two-pointer group tracking approach is the most efficient. It scans the string once while keeping track of the current and previous group lengths of consecutive characters. Whenever the previous group is at least as large as the current one, a valid substring exists. This solution runs in O(n) time with O(1) space.

What data structure is used in Count Binary Substrings?

The problem mainly relies on string traversal and simple counters rather than complex data structures. Some implementations store group counts in an array or list, while the optimal approach only keeps two integer counters representing consecutive character groups.

What is the time complexity of Count Binary Substrings?

The optimal solution runs in O(n) time because the string is scanned once from left to right. Each character contributes to updating group lengths and possibly counting a substring. Space complexity can be O(1) using the two-pointer group tracking method or O(n) if a group count array is stored.

Count Binary Substrings Python or Java solution approach?

Both Python and Java solutions typically implement the two-pointer group tracking technique. Iterate through the string, track the current run length of identical characters, and compare it with the previous run length to count valid substrings. The algorithm runs in O(n) time and uses O(1) extra space.

Is Count Binary Substrings asked at Google, Amazon, or Meta?

Count Binary Substrings is a common easy-level interview problem that appears in coding screens and practice sets used by companies like Amazon, Google, and Meta. It tests pattern recognition in strings and the ability to reduce space complexity while maintaining linear time performance.

Count Binary Substrings solution and explanation

The problem

Approach overview

Approach 1: Two-Pointer Approach

Approach 2: Group Count Array Approach

Approach 3: Iteration and Counting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Count Binary Substrings solution and explanation

The problem

Approach overview

Approach 1: Two-Pointer Approach

Approach 2: Group Count Array Approach

Approach 3: Iteration and Counting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems