# Count Binary Substrings
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-binary-substrings)
Canonical: https://scaleengineer.com/dsa/problems/count-binary-substrings
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** String
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [IBM](https://scaleengineer.com/companies/ibm), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Salesforce](https://scaleengineer.com/companies/salesforce)
---
## 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 <= 105`
* `s[i]` is either `'0'` or `'1'`.

# Approaches
## Brute Force - Expand From Center
This approach iterates through the string to find all possible "centers" of a valid substring. A center is a point where the character changes, i.e., a "01" or "10" pattern. For each center found, we expand outwards in both directions, checking if the characters match the initial pattern (e.g., '0's to the left, '1's to the right). We count how many valid substrings can be formed by this expansion.
**Time:** O(N^2), where N is the length of the string. In the worst case, for each of the N potential centers, the expansion could take up to O(N) time. · **Space:** O(1), as we only use a few variables for pointers and the count.
**Pros:** Simple to understand and implement.; It correctly identifies all valid substrings by focusing on their central property.; Uses constant extra space.
**Cons:** The time complexity is quadratic, which is too slow for the given constraints (N up to 10^5) and will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
The core idea is that any valid substring must contain a "01" or "10" boundary. We can iterate through the string with an index `i` from `0` to `n-2`. If `s[i]` is different from `s[i+1]`, we have found a potential center. For example, if we find `s[i] = '0'` and `s[i+1] = '1'`, we have found the valid substring "01". This is our base case. We then try to expand this substring. We use two pointers, `left = i - 1` and `right = i + 2`. We move `left` to the left and `right` to the right as long as `s[left]` is '0' and `s[right]` is '1'. For each successful expansion, we find another valid substring (e.g., "0011", "000111", etc.) and increment our count. We repeat this process for all possible centers in the string.

```java
class Solution {
    public int countBinarySubstrings(String s) {
        int ans = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) != s.charAt(i + 1)) {
                ans++; // For the base case like "01" or "10"
                int left = i - 1;
                int right = i + 2;
                while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(i) && s.charAt(right) == s.charAt(i + 1)) {
                    ans++;
                    left--;
                    right++;
                }
            }
        }
        return ans;
    }
}
```
### Algorithm
- Initialize a counter `result = 0`.
- Loop through the string `s` from `i = 0` to `s.length() - 2`.
- Check if `s.charAt(i) != s.charAt(i+1)`. If they are different, we've found a center.
    - Increment `result` because we found a valid substring of length 2 (e.g., "01" or "10").
    - Initialize `left = i - 1` and `right = i + 2`.
    - Start a while loop to expand outwards: `while (left >= 0 && right < s.length())`.
        - Inside the loop, check if `s.charAt(left) == s.charAt(i)` and `s.charAt(right) == s.charAt(i+1)`.
        - If the characters match the pattern, we've found another valid substring. Increment `result`, and move the pointers: `left--`, `right++`.
        - If they don't match, the expansion for this center is over. Break the inner while loop.
- After the main loop finishes, return `result`.

## Group Consecutive Characters using an Array
A more efficient approach is to first process the string to find the lengths of consecutive blocks of identical characters. For example, "001110" would be represented as `[2, 3, 1]`. A valid substring is formed at the boundary of any two adjacent groups. The number of valid substrings at each boundary is the minimum of the lengths of the two adjacent groups.
**Time:** O(N), where N is the length of the string. We perform two separate linear passes: one to create the `groups` list and another to sum the results. · **Space:** O(N) in the worst case. The `groups` list can contain up to N elements if the string alternates characters at every position (e.g., "010101...").
**Pros:** Much faster than the brute-force approach, with a linear time complexity that passes the constraints.; The logic is straightforward: group, then count.
**Cons:** Requires extra space to store the group lengths, which can be proportional to the input size in the worst case.
### Explanation
The key observation is that any valid substring is composed of two adjacent, consecutive blocks of '0's and '1's of equal length. For instance, "0011" is formed by a block of two '0's and a block of two '1's. We can first iterate through the input string `s` and count the lengths of consecutive identical characters. We store these lengths in a list or array. For `s = "00110011"`, the list of group lengths would be `[2, 2, 2, 2]`. Once we have this list of group lengths, we can iterate through it. For any two adjacent lengths, `groups[i]` and `groups[i+1]`, they represent two adjacent blocks of different characters. The number of valid substrings they can form is `min(groups[i], groups[i+1])`. For example, with groups of length 2 and 3 ("00111"), we can form "01" and "0011". The number is `min(2, 3) = 2`. We sum up these minimums for all adjacent pairs in the group lengths list to get the total count.

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

class Solution {
    public int countBinarySubstrings(String s) {
        List<Integer> groups = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return 0;
        }
        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 ans = 0;
        for (int i = 0; i < groups.size() - 1; i++) {
            ans += Math.min(groups.get(i), groups.get(i + 1));
        }
        return ans;
    }
}
```
### Algorithm
- Create a list of integers, `groups`.
- If the input string `s` is empty, return 0.
- Initialize a counter `count = 1`.
- Iterate through the string from the second character (`i = 1` to `s.length() - 1`):
    - If `s.charAt(i) == s.charAt(i-1)`, increment `count`.
    - Otherwise, the group has ended. Add the current `count` to the `groups` list and reset `count = 1`.
- After the loop, add the last `count` to the `groups` list.
- Initialize `result = 0`.
- Iterate through the `groups` list from `i = 0` to `groups.size() - 2`:
    - Add `Math.min(groups.get(i), groups.get(i+1))` to `result`.
- Return `result`.

## Optimized Linear Scan with Constant Space
This is the most optimal approach. It builds upon the grouping idea but eliminates the need for an auxiliary array to store group lengths. By iterating through the string once, we can compute the group lengths on the fly and maintain only the lengths of the current and previous groups.
**Time:** O(N), where N is the length of the string. We iterate through the string only once. · **Space:** O(1). We only use a few constant-size variables to store the counts.
**Pros:** Highly efficient in both time and space.; It's the optimal solution for this problem, passing all constraints with ease.
**Cons:** The logic might be slightly less intuitive at first glance compared to the approach that explicitly stores group lengths.
### Explanation
We can observe from the previous approach that to calculate the result, we only need the lengths of two adjacent groups at any given time. This means we don't need to store all group lengths. We can use two variables, `prevGroupLength` and `currGroupLength`, to keep track of the lengths of the previous and current consecutive blocks of characters. We iterate through the string. As we encounter a new group of characters (i.e., when `s[i] != s[i-1]`), the `currGroupLength` of the just-finished group is now known. We can then calculate the number of valid substrings formed by this group and the `prevGroupLength` by taking their minimum. After processing the boundary, the `currGroupLength` becomes the new `prevGroupLength` for the next iteration, and we reset `currGroupLength` to 1 for the new group we've just started.

```java
class Solution {
    public int countBinarySubstrings(String s) {
        int ans = 0;
        int prevGroupLength = 0;
        int currGroupLength = 1;

        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                currGroupLength++;
            } else {
                ans += Math.min(prevGroupLength, currGroupLength);
                prevGroupLength = currGroupLength;
                currGroupLength = 1;
            }
        }
        // Add the last comparison
        ans += Math.min(prevGroupLength, currGroupLength);
        return ans;
    }
}
```
### Algorithm
- Initialize `result = 0`, `prevGroupLength = 0`, and `currGroupLength = 1`.
- Iterate through the string `s` from `i = 1` to `s.length() - 1`.
    - If `s.charAt(i) == s.charAt(i-1)`, it's part of the same group, so increment `currGroupLength`.
    - If `s.charAt(i) != s.charAt(i-1)`, a group has just ended.
        - Add `Math.min(prevGroupLength, currGroupLength)` to `result`.
        - The current group now becomes the previous group for the next boundary, so set `prevGroupLength = currGroupLength`.
        - Reset `currGroupLength = 1` for the new group starting at `i`.
- After the loop, there's one last group to account for. Add `Math.min(prevGroupLength, currGroupLength)` to `result` one more time.
- Return `result`.

# Solutions
### Java

```java
class Solution {
public
  int countBinarySubstrings(String s) {
    int i = 0, n = s.length();
    List<Integer> t = new ArrayList<>();
    while (i < n) {
      int cnt = 1;
      while (i + 1 < n && s.charAt(i + 1) == s.charAt(i)) {
        ++i;
        ++cnt;
      }
      t.add(cnt);
      ++i;
    }
    int ans = 0;
    for (i = 1; i < t.size(); ++i) {
      ans += Math.min(t.get(i - 1), t.get(i));
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution { public: int countBinarySubstrings ( string s ) { int i = 0 , n = s . size (); vector < int > t ; while ( i < n ) { int cnt = 1 ; while ( i + 1 < n && s [ i + 1 ] == s [ i ]) { ++ cnt ; ++ i ; } t . push_back ( cnt ); ++ i ; } int ans = 0 ; for ( i = 1 ; i < t . size (); ++ i ) ans += min ( t [ i - 1 ], t [ i ]); return ans ; } };
```

### Python

```python
class Solution : def countBinarySubstrings ( self , s : str ) -> int : i , n = 0 , len ( s ) t = [] while i < n : cnt = 1 while i + 1 < n and s [ i + 1 ] == s [ i ]: cnt += 1 i += 1 t . append ( cnt ) i += 1 ans = 0 for i in range ( 1 , len ( t )): ans += min ( t [ i - 1 ], t [ i ]) return ans
```