Count the number of substrings with dominant ones

String Enumeration

42.1% acceptance

Feb 25, 2026

632

169

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.

Solution

Rust

Time O(n³)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_substrings(s: String) -> i32 {
    let bytes = s.as_bytes();
    let n = bytes.len();
    // Positions of zeros
    let zeros: Vec<usize> = (0..n).filter(|&i| bytes[i] == b'0').collect();
    let nz = zeros.len();
    let mut count = 0i64;

    // z = 0: all-one substrings -> count runs of 1s
    let mut run = 0i64;
    for i in 0..n {
      if bytes[i] == b'1' {
        run += 1;
        count += run;
      } else {
        run = 0;
      }
    }

    // z >= 1: for each z where z^2 <= n
    let mut z = 1usize;
    while z * z <= n {
      let min_len = z * (z + 1); // substring needs >= min_len chars (z zeros + z^2 ones)
      for i in 0..nz {
        if i + z > nz { break; }
        let first_zero = zeros[i];
        let last_zero = zeros[i + z - 1];
        let ls = if i == 0 { 0 } else { zeros[i - 1] + 1 };
        let re = if i + z == nz { n - 1 } else { zeros[i + z] - 1 };

        // start s in [ls, first_zero], need end e >= max(last_zero, s + min_len - 1), e <= re
        for start in ls..=first_zero {
          let min_end = last_zero.max(start + min_len - 1);
          if min_end <= re {
            count += (re - min_end + 1) as i64;
          }
        }
      }
      z += 1;
    }
    count as i32
  }
}