Count Binary Substrings
Easy · Arrays & Hashing · Two Pointers · String
Problem
You are given a binary string s. Count the non-empty substrings that contain the same number of 0s and 1s, where all the 0s are consecutive and all the 1s are consecutive — so the substring looks like 0…01…1 or 1…10…0.
Substrings that are equal but start at different positions are counted separately.
Examples
Input: s = "0011100" Output: 4
The runs have lengths 2, 3, 2. The first border gives "01" and "0011", the second "10" and "1100".
Input: s = "0101" Output: 3
"01", "10" and "01" each qualify. "0101" does not: its 0s are not consecutive.
Input: s = "111" Output: 0
There are no 0s at all.
Constraints
- 1 <= len(s) <= 10^5
- s[i] is either '0' or '1'
Approaches
- Baseline: check every start — time O(n²) worst case, space O(1)
Follow-up
What if the string uses any two letters, or you are asked for the substrings themselves? The count stays O(n) with runs. Listing them can take O(n²) output on a string like 0…01…1, so no algorithm can do better than the output size.
Related problems
Start free on Cariara · Coding problems · System design studio
