Count Binary Substrings

Easy
241.

Count Binary Substrings

Count Binary Substrings is an easy coding problem on strings and two pointers, asked in Amazon and Google interviews.

Given a binary string s, count the non-empty substrings that have the same number of 0s and 1s, with all the 0s and all the 1s grouped consecutively.

Substrings that occur multiple times are counted once per occurrence.

Example 1

Input
s = "00110011"
Output
6
Explanation
The qualifying substrings are "0011", "01", "1100", "10", "0011" and "01".

Example 2

Input
s = "10101"
Output
4

Example 3

Input
s = "000"
Output
0

Constraints

  • 1 <= s.length <= 40
  • s[i] is '0' or '1'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var countBinarySubstrings = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Binary Substrings — Solution in Python, Java & C++

Count Binary Substrings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Count Binary Substrings is an easy coding problem on strings and two pointers, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Strings, Two Pointers
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a binary string s, count the non-empty substrings that have the same number of 0s and 1s, with all the 0s and all the 1s grouped consecutively.

Substrings that occur multiple times are counted once per occurrence.

Example 1

Input: s = "00110011"
Output: 6
Explanation: The qualifying substrings are "0011", "01", "1100", "10", "0011" and "01".

Example 2

Input: s = "10101"
Output: 4

Example 3

Input: s = "000"
Output: 0

Constraints

  • 1 <= s.length <= 40
  • s[i] is '0' or '1'.

Hints for Count Binary Substrings

  1. Hint 1

    Only runs of equal characters matter — compress the string into a list of run lengths.

  2. Hint 2

    Each adjacent pair of runs contributes min(previous, current) valid substrings.

  3. Hint 3

    You can keep just the previous and current run lengths and never build the list at all.

How to solve Count Binary Substrings

Compress the string into run lengths; each adjacent pair of runs contributes min(prev, cur) valid substrings.

Approach

  1. Scan the string, collecting the length of each maximal run of equal characters.
  2. Sum min(groups[k-1], groups[k]) over consecutive pairs.

Why it works

A valid substring is 0^m 1^m or 1^m 0^m, which must be centred on a boundary between two runs and can extend m characters into each — at most the shorter run's length. Different boundaries give different substrings, so the sums add.

Complexity

  • Time — O(n)
  • Space — O(n) for the run list (O(1) keeping just prev/cur)

Pitfalls

  • Substrings are counted per occurrence, which the per-boundary sum does automatically.

Reference solution

Python

def countBinarySubstrings(s: str) -> int:
    groups = []
    i = 0
    while i < len(s):
        j = i
        while j < len(s) and s[j] == s[i]:
            j += 1
        groups.append(j - i)
        i = j
    return sum(min(groups[k - 1], groups[k]) for k in range(1, len(groups)))

Java

public static int countBinarySubstrings(String s) {
    int prev = 0, cur = 0, total = 0;
    for (int i = 0; i < s.length(); i++) {
        if (i > 0 && s.charAt(i) != s.charAt(i - 1)) {
            prev = cur;
            cur = 1;
        } else {
            cur++;
        }
        if (prev >= cur) total++;
    }
    return total;
}

C++

int countBinarySubstrings(string s) {
    int prev = 0, cur = 0, total = 0;
    for (int i = 0; i < (int) s.size(); i++) {
        if (i > 0 && s[i] != s[i - 1]) {
            prev = cur;
            cur = 1;
        } else {
            cur++;
        }
        if (prev >= cur) total++;
    }
    return total;
}

JavaScript

var countBinarySubstrings = function(s) {
    const groups = [];
    let i = 0;
    while (i < s.length) {
        let j = i;
        while (j < s.length && s[j] === s[i]) j++;
        groups.push(j - i);
        i = j;
    }
    let total = 0;
    for (let k = 1; k < groups.length; k++) {
        total += Math.min(groups[k - 1], groups[k]);
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Two Pointers Technique