# LeetCode 696: Count Binary Substrings

## Problem Restatement

We are given a binary string `s`.

We need to count non-empty substrings that satisfy both rules:

| Rule | Meaning |
|---|---|
| Equal counts | The substring has the same number of `0`s and `1`s |
| Grouped characters | All `0`s are consecutive and all `1`s are consecutive |

Substrings that appear multiple times are counted multiple times. For example, `"00110011"` has two separate occurrences of `"0011"` and two separate occurrences of `"01"`, and each occurrence counts.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A binary string `s` |
| Output | Number of valid substrings |
| Characters | Only `'0'` and `'1'` |
| Constraint | `1 <= s.length <= 10^5` |

Example function shape:

```python
def countBinarySubstrings(s: str) -> int:
    ...
```

## Examples

Example 1:

```python
s = "00110011"
```

Valid substrings are:

```text
"0011"
"01"
"1100"
"10"
"0011"
"01"
```

Answer:

```python
6
```

The full string `"00110011"` is not valid because the `0`s and `1`s are split into multiple groups.

Example 2:

```python
s = "10101"
```

Valid substrings are:

```text
"10"
"01"
"10"
"01"
```

Answer:

```python
4
```

## First Thought: Check Every Substring

A direct solution is to generate every substring and test whether:

1. it has the same number of `0`s and `1`s,
2. it has only one group of `0`s and one group of `1`s.

This works logically, but there are `O(n^2)` substrings.

Checking each substring also costs time, so this approach is too slow for large input.

## Key Insight

A valid substring must cross exactly one boundary between two groups.

For example:

```text
000111
```

has two groups:

| Group | Length |
|---|---:|
| `000` | `3` |
| `111` | `3` |

Valid substrings around this boundary are:

```text
01
0011
000111
```

There are `3` of them.

Now consider:

```text
00011
```

The group lengths are `3` and `2`.

Valid substrings are:

```text
01
0011
```

There are:

```text
min(3, 2) = 2
```

So every adjacent pair of groups contributes:

```text
min(previous_group_length, current_group_length)
```

valid substrings.

## Algorithm

Track two group lengths while scanning:

| Variable | Meaning |
|---|---|
| `prev` | Length of the previous consecutive character group |
| `curr` | Length of the current consecutive character group |

Initialize:

```python
prev = 0
curr = 1
answer = 0
```

Then scan from index `1` to the end.

If the current character equals the previous character:

```python
curr += 1
```

we are still inside the same group.

Otherwise, the group changed.

At that boundary:

```python
answer += min(prev, curr)
prev = curr
curr = 1
```

After the loop, add the contribution from the final adjacent group pair:

```python
answer += min(prev, curr)
```

Return `answer`.

## Walkthrough

Consider:

```python
s = "00110011"
```

The groups are:

```text
00 | 11 | 00 | 11
```

Group lengths:

```python
[2, 2, 2, 2]
```

Adjacent group contributions:

| Adjacent groups | Contribution |
|---|---:|
| `00`, `11` | `min(2, 2) = 2` |
| `11`, `00` | `min(2, 2) = 2` |
| `00`, `11` | `min(2, 2) = 2` |

Total:

```text
2 + 2 + 2 = 6
```

Answer:

```python
6
```

Now consider:

```python
s = "10101"
```

The groups are:

```text
1 | 0 | 1 | 0 | 1
```

Group lengths:

```python
[1, 1, 1, 1, 1]
```

There are four adjacent group pairs, each contributing `1`.

Answer:

```python
4
```

## Correctness

Every valid substring contains exactly two consecutive groups: one group of `0`s and one group of `1`s.

It cannot contain more than two groups, because then either the `0`s or the `1`s would be split apart and would not be grouped consecutively.

For any two adjacent groups with lengths `a` and `b`, a valid substring can use `x` characters from the end of the first group and `x` characters from the start of the second group.

The value of `x` can be any integer from `1` through `min(a, b)`.

So this adjacent pair contributes exactly `min(a, b)` valid substrings.

The algorithm scans the string and computes each group length. At every group boundary, it adds the contribution from the previous adjacent pair. After the scan, it adds the last pair.

Therefore, every valid substring is counted once, and no invalid substring is counted.

## Complexity

Let `n = len(s)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | We scan the string once |
| Space | `O(1)` | Only counters are stored |

## Implementation

```python
class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        answer = 0
        prev = 0
        curr = 1

        for i in range(1, len(s)):
            if s[i] == s[i - 1]:
                curr += 1
            else:
                answer += min(prev, curr)
                prev = curr
                curr = 1

        answer += min(prev, curr)

        return answer
```

## Code Explanation

We use:

```python
prev = 0
curr = 1
```

At the start, there is no previous group yet, and the current group contains the first character.

When adjacent characters are equal:

```python
if s[i] == s[i - 1]:
    curr += 1
```

we extend the current group.

When the character changes:

```python
answer += min(prev, curr)
```

we finish one adjacent group pair and add its contribution.

Then the old current group becomes the previous group:

```python
prev = curr
```

and the new current group starts with length `1`:

```python
curr = 1
```

After the loop, the final pair has not been added yet, so we add it:

```python
answer += min(prev, curr)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.countBinarySubstrings("00110011") == 6
    assert s.countBinarySubstrings("10101") == 4

    assert s.countBinarySubstrings("0") == 0
    assert s.countBinarySubstrings("01") == 1
    assert s.countBinarySubstrings("00110") == 3
    assert s.countBinarySubstrings("000111") == 3
    assert s.countBinarySubstrings("00011") == 2
    assert s.countBinarySubstrings("111000111") == 6

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Expected | Why |
|---|---:|---|
| `"00110011"` | `6` | Official example |
| `"10101"` | `4` | Official example |
| `"0"` | `0` | No opposite bit group |
| `"01"` | `1` | One valid substring |
| `"00110"` | `3` | Contributions `2 + 1` |
| `"000111"` | `3` | Three balanced substrings |
| `"00011"` | `2` | Limited by smaller group |
| `"111000111"` | `6` | Two boundaries, each contributes `3` |