Input: s ="00011"Output: 5Explanation:
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|14|4|1|0|12|3|01|1|13|4|11|0|22|4|011|1|2
Input: s ="101101"Output: 16Explanation:
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|04|4|0|1|01|4|0110|2|20|4|10110|2|31|5|01101|2|3
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.
classSolution {
funcountDominantOnes(s: String): Long {
val n = s.length
val ones = IntArray(n+1)
val zeros = IntArray(n+1)
for (i in0 until n) {
ones[i+1] = ones[i] + if (s[i] =='1') 1else0 zeros[i+1] = zeros[i] + if (s[i] =='0') 1else0 }
var ans = 0Lval zeroPos = mutableMapOf<Int, MutableList<Int>>()
for (i in0..n) {
zeroPos.getOrPut(zeros[i]) { mutableListOf() }.add(i)
}
for (z in0..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
}
}
classSolution:
defcountDominantOnes(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 =0for 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 +=1return ans
impl Solution {
pubfncount_dominant_ones(s: String) -> i64 {
let n = s.len();
let s = s.as_bytes();
letmut ones =vec![0; n+1];
letmut zeros =vec![0; n+1];
for i in0..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 };
}
letmut zero_pos = std::collections::HashMap::new();
for i in0..=n {
zero_pos.entry(zeros[i]).or_insert(vec![]).push(i);
}
letmut ans =0i64;
for z in0..=zeros[n] {
iflet Some(pos) = zero_pos.get(&z) {
for i in0..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
}
}