Balanced Binary Substrings
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
Given a binary string s, count the non-empty substrings that have the same number of 0s and 1s, where all 0s are
consecutive and all 1s are consecutive (like 000111 or 10, but not 0101). Substrings at different positions are counted
separately.
Examples
| s | result |
|---|---|
"00110011" | 6 |
"10101" | 4 |
"000" | 0 |
Example 1 — "0011", "01", "1100", "10", "0011", "01".
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(s: string) → int
Constraints
-
s.length, only0and1
Expected complexity
- Time
- O(N)
- Space
- O(1)
Examples
| s | Expected |
|---|---|
"00110011" | 6 |
"10101" | 4 |
"000" | 0 |
Hint
Hint
Every valid substring straddles the boundary between two adjacent runs of equal characters. If two adjacent runs have lengths
a and b, that boundary contributes exactly min(a, b) substrings. Sweep once remembering the previous and current run
lengths. Extending from every start position is on long runs and exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1000 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 10 | verdict only |
| performance | 60 | 4 | verdict only |