Code Logo

Count Binary Substrings

Published at23 Jul 2026
Created by
Easy 1 views
Like0

Given a binary string, count substrings that have equal numbers of 0s and 1s where all 0s and 1s are grouped consecutively. Substrings can overlap. For example, "00110011" has 6 valid substrings. The approach groups consecutive identical characters by length. For each adjacent pair of groups (which are always different characters), the number of valid substrings is the minimum of the two group lengths. A stack stores group lengths as they are completed, then adjacent pairs are summed.

A group-based approach without a stack also works: iterate through the string, counting consecutive 0s and 1s. When the character changes, record the current group length and start counting the next group. Then iterate through the group lengths, and for each adjacent pair of groups, add the minimum of the two lengths to the result. This works because each valid substring must cross the boundary between two groups of different characters, and the number of valid substrings crossing that boundary is limited by the smaller of the two groups.

The stack stores group lengths as they are completed, making it easy to compare adjacent pairs at the end.

A stack approach iterates through the string, grouping consecutive identical characters and recording the length of each group. Then, for each adjacent pair of groups, the number of valid substrings is the minimum of the two group lengths. This works because each valid substring must span the boundary between two groups, and the number of substrings that can cross that boundary is limited by the smaller group. Substrings can also overlap, which is naturally accounted for by summing across all adjacent group boundaries.

Example Input & Output

Example 1
Input
"10101"
Output
4
Explanation

Groups [1,1,1,1,1].

Example 2
Input
"00110011"
Output
6
Explanation

Groups [2,2,2,2].

Example 3
Input
"00110"
Output
3
Explanation

Groups [2,2,1].

Algorithm Flow

Recommendation Algorithm Flow for Count Binary Substrings
Recommendation Algorithm Flow for Count Binary Substrings

Solution Approach

Count consecutive same chars. When char changes, push count. After loop, sum min of adjacent pairs.

function solution(s) {
  var groups = [];
  var count = 1;
  for (var i = 1; i < s.length; i++) {
    if (s[i] === s[i-1]) count++;
    else { groups.push(count); count = 1; }
  }
  groups.push(count);
  var result = 0;
  for (var i = 1; i < groups.length; i++)
    result += Math.min(groups[i-1], groups[i]);
  return result;
}

Time O(n), Space O(n).

Best Answers

java
import java.util.*;
class Solution {
    public int solution(String s) {
        List<Integer> groups = new ArrayList<>();
        int count = 1;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i-1)) count++;
            else { groups.add(count); count = 1; }
        }
        groups.add(count);
        int result = 0;
        for (int i = 1; i < groups.size(); i++)
            result += Math.min(groups.get(i-1), groups.get(i));
        return result;
    }
}