Funcia
Lv.1countingstring

Balanced Binary Substrings

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

sresult
"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

  • 1≤1 \le s.length ≤500,000\le 500{,}000, only 0 and 1

Expected complexity

Time
O(N)
Space
O(1)

Examples

sExpected
"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 O(N2)O(N^2) on long runs and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.