Count the Number of Substrings With Dominant Ones
MediumUpdated: Aug 2, 2025
Practice on:
Problem
You are given a binary string s.
Return the number of substrings with dominant ones.
A string has dominant ones if the number of ones in the string is greater than or equal to the square of the number of zeros in the string.
Examples
Example 1
Input: s = "00011"
Output: 5
Explanation:
The substrings with dominant ones are shown in the table below.
i | j | s[i..j] | Number of Zeros | Number of Ones
---|---|---|---|---
3 | 3 | 1 | 0 | 1
4 | 4 | 1 | 0 | 1
2 | 3 | 01 | 1 | 1
3 | 4 | 11 | 0 | 2
2 | 4 | 011 | 1 | 2
Example 2
Input: s = "101101"
Output: 16
Explanation:
The substrings with **non-dominant** ones are shown in the table below.
Since there are 21 substrings total and 5 of them have non-dominant ones, it
follows that there are 16 substrings with dominant ones.
i | j | s[i..j] | Number of Zeros | Number of Ones
---|---|---|---|---
1 | 1 | 0 | 1 | 0
4 | 4 | 0 | 1 | 0
1 | 4 | 0110 | 2 | 2
0 | 4 | 10110 | 2 | 3
1 | 5 | 01101 | 2 | 3
Constraints
1 <= s.length <= 4 * 10^4sconsists only of characters'0'and'1'.
Solution
Method 1 – Prefix Sums and Sliding Window
Intuition
We want to count substrings where the number of ones is at least the square of the number of zeros. Since the constraint involves the square of zeros, we can use prefix sums to efficiently count ones and zeros in any substring, and for each possible number of zeros, use a sliding window to find valid substrings.
Approach
- Precompute prefix sums for ones and zeros.
- For each possible starting index, keep a map of zero counts to their earliest index.
- For each ending index, for all possible zero counts, check if the substring from the earliest index to the current index has enough ones.
- Use a sliding window to efficiently count substrings with dominant ones.
Code
C++
class Solution {
public:
long long countDominantOnes(string s) {
int n = s.size();
vector<int> ones(n+1), zeros(n+1);
for (int i = 0; i < n; ++i) {
ones[i+1] = ones[i] + (s[i] == '1');
zeros[i+1] = zeros[i] + (s[i] == '0');
}
long long ans = 0;
unordered_map<int, vector<int>> zeroPos;
for (int i = 0; i <= n; ++i) {
zeroPos[zeros[i]].push_back(i);
}
for (int z = 0; z <= zeros[n]; ++z) {
auto& pos = zeroPos[z];
for (int i = 0; i < pos.size(); ++i) {
for (int j = i+1; j < pos.size(); ++j) {
int l = pos[i], r = pos[j];
int oneCnt = ones[r] - ones[l];
if (oneCnt >= z * z) ans++;
}
}
}
return ans;
}
};
Go
func countDominantOnes(s string) int64 {
n := len(s)
ones := make([]int, n+1)
zeros := make([]int, n+1)
for i := 0; i < n; i++ {
ones[i+1] = ones[i]
zeros[i+1] = zeros[i]
if s[i] == '1' {
ones[i+1]++
} else {
zeros[i+1]++
}
}
ans := int64(0)
zeroPos := map[int][]int{}
for i := 0; i <= n; i++ {
zeroPos[zeros[i]] = append(zeroPos[zeros[i]], i)
}
for z := 0; z <= zeros[n]; z++ {
pos := zeroPos[z]
for i := 0; i < len(pos); i++ {
for j := i+1; j < len(pos); j++ {
l, r := pos[i], pos[j]
oneCnt := ones[r] - ones[l]
if oneCnt >= z*z {
ans++
}
}
}
}
return ans
}
Java
class Solution {
public long countDominantOnes(String s) {
int n = s.length();
int[] ones = new int[n+1], zeros = new int[n+1];
for (int i = 0; i < n; i++) {
ones[i+1] = ones[i] + (s.charAt(i) == '1' ? 1 : 0);
zeros[i+1] = zeros[i] + (s.charAt(i) == '0' ? 1 : 0);
}
long ans = 0;
Map<Integer, List<Integer>> zeroPos = new HashMap<>();
for (int i = 0; i <= n; i++) {
zeroPos.computeIfAbsent(zeros[i], k -> new ArrayList<>()).add(i);
}
for (int z = 0; z <= zeros[n]; z++) {
List<Integer> pos = zeroPos.get(z);
for (int i = 0; i < pos.size(); i++) {
for (int j = i+1; j < pos.size(); j++) {
int l = pos.get(i), r = pos.get(j);
int oneCnt = ones[r] - ones[l];
if (oneCnt >= z * z) ans++;
}
}
}
return ans;
}
}
Kotlin
class Solution {
fun countDominantOnes(s: String): Long {
val n = s.length
val ones = IntArray(n+1)
val zeros = IntArray(n+1)
for (i in 0 until n) {
ones[i+1] = ones[i] + if (s[i] == '1') 1 else 0
zeros[i+1] = zeros[i] + if (s[i] == '0') 1 else 0
}
var ans = 0L
val zeroPos = mutableMapOf<Int, MutableList<Int>>()
for (i in 0..n) {
zeroPos.getOrPut(zeros[i]) { mutableListOf() }.add(i)
}
for (z in 0..zeros[n]) {
val pos = zeroPos[z]!!
for (i in pos.indices) {
for (j in i+1 until pos.size) {
val l = pos[i]; val r = pos[j]
val oneCnt = ones[r] - ones[l]
if (oneCnt >= z * z) ans++
}
}
}
return ans
}
}
Python
class Solution:
def countDominantOnes(self, s: str) -> int:
n = len(s)
ones = [0] * (n+1)
zeros = [0] * (n+1)
for i in range(n):
ones[i+1] = ones[i] + (s[i] == '1')
zeros[i+1] = zeros[i] + (s[i] == '0')
from collections import defaultdict
zero_pos = defaultdict(list)
for i in range(n+1):
zero_pos[zeros[i]].append(i)
ans = 0
for z in range(zeros[n]+1):
pos = zero_pos[z]
for i in range(len(pos)):
for j in range(i+1, len(pos)):
l, r = pos[i], pos[j]
one_cnt = ones[r] - ones[l]
if one_cnt >= z * z:
ans += 1
return ans
Rust
impl Solution {
pub fn count_dominant_ones(s: String) -> i64 {
let n = s.len();
let s = s.as_bytes();
let mut ones = vec![0; n+1];
let mut zeros = vec![0; n+1];
for i in 0..n {
ones[i+1] = ones[i] + if s[i] == b'1' { 1 } else { 0 };
zeros[i+1] = zeros[i] + if s[i] == b'0' { 1 } else { 0 };
}
let mut zero_pos = std::collections::HashMap::new();
for i in 0..=n {
zero_pos.entry(zeros[i]).or_insert(vec![]).push(i);
}
let mut ans = 0i64;
for z in 0..=zeros[n] {
if let Some(pos) = zero_pos.get(&z) {
for i in 0..pos.len() {
for j in i+1..pos.len() {
let l = pos[i]; let r = pos[j];
let one_cnt = ones[r] - ones[l];
if one_cnt >= z * z {
ans += 1;
}
}
}
}
}
ans
}
}
TypeScript
class Solution {
countDominantOnes(s: string): number {
const n = s.length
const ones = new Array(n+1).fill(0)
const zeros = new Array(n+1).fill(0)
for (let i = 0; i < n; ++i) {
ones[i+1] = ones[i] + (s[i] === '1' ? 1 : 0)
zeros[i+1] = zeros[i] + (s[i] === '0' ? 1 : 0)
}
const zeroPos: Record<number, number[]> = {}
for (let i = 0; i <= n; ++i) {
if (!zeroPos[zeros[i]]) zeroPos[zeros[i]] = []
zeroPos[zeros[i]].push(i)
}
let ans = 0
for (let z = 0; z <= zeros[n]; ++z) {
const pos = zeroPos[z]
for (let i = 0; i < pos.length; ++i) {
for (let j = i+1; j < pos.length; ++j) {
const l = pos[i], r = pos[j]
const oneCnt = ones[r] - ones[l]
if (oneCnt >= z * z) ans++
}
}
}
return ans
}
}
Complexity
- ⏰ Time complexity:
O(n^2)in the worst case (when all zeros are grouped together), but typically much faster for random strings. - 🧺 Space complexity:
O(n)for prefix sums and maps.