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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


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^4
  • s consists 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

  1. Precompute prefix sums for ones and zeros.
  2. For each possible starting index, keep a map of zero counts to their earliest index.
  3. For each ending index, for all possible zero counts, check if the substring from the earliest index to the current index has enough ones.
  4. Use a sliding window to efficiently count substrings with dominant ones.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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.