Count the Number of Substrings With Dominant Ones solution and explanation
Google
9 more videos on this problem
Count the Number of Substrings With Dominant Ones | Brute Force | Improved | Leetcode 3234 | MIKcodestorywithMIK · 38:03 · 12K views
Count the Number of Substrings With Dominant Ones - Leetcode 3234 - PythonNeetCodeIO · 30:35 · 9K views
3234. Count the Number of Substrings With Dominant Ones | Weekly Leetcode 408codingMohan · 28:34 · 7K views
3234 Count the Number of Substrings With Dominant OnesCodeCracker · 17:20 · 2K views
Count Substrings With Dominant Ones | LeetCode 3234 | Complete Intution ExplainedSanyam IIT Guwahati · 23:36 · 2K views
3234. Count the Number of Substrings With Dominant Ones (Leetcode Medium)Programming Live with Larry · 1:53:34 · 1K views
3234. Count the Number of Substrings With Dominant Ones | Leetcode Daily - PythonLeetcode Daily · 8:42 · 861 views
【每日一题】LeetCode 3234. Count the Number of Substrings With Dominant OnesHuifeng Guan · 40:00 · 767 views
Daily Leetcode #2055: Nov 15, 2025 - 3234. Count the Number of Substrings With Dominant OnesProgramming Live with Larry · 53:40 · 715 views
LeetCode 3234 🔥 Count Substrings With Dominant Ones | DCC | Sliding Window + Zero-Count Logic Study Placement · 25:34 · 559 views
The 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.
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 * 104sconsists only of characters'0'and'1'.
Approach overview
Problem Overview: Given a binary string, count the number of substrings where the number of 1s is at least the square of the number of 0s. Every substring must satisfy ones ≥ zeros². The challenge is efficiently checking this condition across all substrings without scanning each substring repeatedly.
Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)
Generate every substring using two nested loops. For each starting index, extend the substring one character at a time and maintain running counts of 0s and 1s. After each extension, check the condition ones ≥ zeros * zeros. This avoids recomputing counts from scratch but still examines every possible substring, resulting in quadratic time. The method is straightforward and useful for validating logic during development, but it becomes slow when the string length grows.
Approach 2: Enumeration with Prefix Sum Optimization (O(n√n) time, O(n) space)
The constraint ones ≥ zeros² severely limits how many zeros a valid substring can contain. If a substring has k zeros, it must have at least k² ones, so the length must be at least k² + k. For a string of length n, k cannot exceed roughly √n. Use this observation to enumerate substrings by the number of zeros instead of their full length.
Precompute prefix sums of ones so the number of ones in any substring can be retrieved in constant time. Then iterate through the string and expand candidate substrings while tracking the number of zeros. Because the zero count is capped at about √n, each starting position only considers a limited number of expansions. Prefix sums make each validity check constant time, significantly reducing repeated counting work.
This technique combines enumeration with fast range queries from prefix sum. A sliding window-style expansion keeps substring construction efficient while respecting the zero bound.
Recommended for interviews: Start by explaining the brute force approach to show you understand the substring enumeration process. Then introduce the key mathematical observation that the number of zeros is bounded by √n. Using prefix sums to evaluate substrings quickly demonstrates strong optimization skills and typically matches the expected interview solution.
Approach 1: Brute Force Approach
This approach involves checking each substring of s. For each substring, count the number of ones and zeros, then determine if the substring has dominant ones. This method is straightforward but may be inefficient for large strings.
def dominant_substrings(s):
count = 0
for i in range(len(s)):
ones = zeros = 0
for j in range(i, len(s)):
if s[j] == '1':
ones += 1
else:
zeros += 1
if ones >= zeros ** 2:
count += 1
return count
s = "101101"
print(dominant_substrings(s)) # Output: 16public class Main {
public static int dominantSubstrings(String s) {
int len = s.length(), count = 0;
for (int i = 0; i < len; i++) {
int ones = 0, zeros = 0;
for (int j = i; j < len; j++) {
if (s.charAt(j) == '1') ones++;
else zeros++;
if (ones >= zeros * zeros) count++;
}
}
return count;
}
public static void main(String[] args) {
String s = "00011";
System.out.println(dominantSubstrings(s)); // Output: 5
}
}#include <iostream>
#include <string>
using namespace std;
int dominantSubstrings(string s) {
int len = s.length(), count = 0;
for (int i = 0; i < len; i++) {
int ones = 0, zeros = 0;
for (int j = i; j < len; j++) {
if (s[j] == '1') ones++;
else zeros++;
if (ones >= zeros * zeros) count++;
}
}
return count;
}
int main() {
string s = "101101";
cout << dominantSubstrings(s) << endl; // Output: 16
return 0;
}function dominantSubstrings(s) {
let count = 0;
for (let i = 0; i < s.length; i++) {
let ones = 0, zeros = 0;
for (let j = i; j < s.length; j++) {
if (s[j] === '1') ones++;
else zeros++;
if (ones >= zeros * zeros) count++;
}
}
return count;
}
const s = "00011";
console.log(dominantSubstrings(s)); // Output: 5#include <stdio.h>
#include <string.h>
int dominantSubstrings(char* s) {
int len = strlen(s), count = 0;
for (int i = 0; i < len; i++) {
int ones = 0, zeros = 0;
for (int j = i; j < len; j++) {
if (s[j] == '1') ones++;
else zeros++;
if (ones >= zeros * zeros) count++;
}
}
return count;
}
int main() {
char s[] = "00011";
printf("%d\n", dominantSubstrings(s)); // Output: 5
return 0;
}using System;
class Program {
static int DominantSubstrings(string s) {
int len = s.Length, count = 0;
for (int i = 0; i < len; i++) {
int ones = 0, zeros = 0;
for (int j = i; j < len; j++) {
if (s[j] == '1') ones++;
else zeros++;
if (ones >= zeros * zeros) count++;
}
}
return count;
}
static void Main() {
string s = "101101";
Console.WriteLine(DominantSubstrings(s)); // Output: 16
}
}The Python function employs nested loops to examine each substring. It assesses dominance by comparing the count of ones to the square of zeros.
Time Complexity: O(n^3), considering three levels of loops.
Space Complexity: O(1), since no extra space is used except for counting variables.
Approach 2: Optimized Approach with Prefix Sum
This approach optimizes the search for all possible substrings using prefix sums. It calculates cumulative counts of ones and zeros, allowing efficient evaluation of the dominance condition by comparing only the difference between indices.
def dominant_substrings(s):
n = len(s)
prefix_ones = [0] * (n + 1)
prefix_zeros = [0] * (n + 1)
count = 0
for i in range(n):
prefix_ones[i + 1] = prefix_ones[i] + (1 if s[i] == '1' else 0)
prefix_zeros[i + 1] = prefix_zeros[i] + (1 if s[i] == '0' else 0)
for start in range(n):
for end in range(start, n):
ones = prefix_ones[end + 1] - prefix_ones[start]
zeros = prefix_zeros[end + 1] - prefix_zeros[start]
if ones >= zeros ** 2:
count += 1
return count
s = "00011"
print(dominant_substrings(s)) # Output: 5public class Main {
public static int dominantSubstrings(String s) {
int n = s.length(), count = 0;
int[] prefixOnes = new int[n + 1];
int[] prefixZeros = new int[n + 1];
for (int i = 0; i < n; i++) {
prefixOnes[i + 1] = prefixOnes[i] + (s.charAt(i) == '1' ? 1 : 0);
prefixZeros[i + 1] = prefixZeros[i] + (s.charAt(i) == '0' ? 1 : 0);
}
for (int start = 0; start < n; start++) {
for (int end = start; end < n; end++) {
int ones = prefixOnes[end + 1] - prefixOnes[start];
int zeros = prefixZeros[end + 1] - prefixZeros[start];
if (ones >= zeros * zeros) count++;
}
}
return count;
}
public static void main(String[] args) {
String s = "101101";
System.out.println(dominantSubstrings(s)); // Output: 16
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
int dominantSubstrings(string s) {
int count = 0, n = s.size();
vector<int> prefixOnes(n+1, 0);
vector<int> prefixZeros(n+1, 0);
for (int i = 0; i < n; i++) {
prefixOnes[i+1] = prefixOnes[i] + (s[i] == '1');
prefixZeros[i+1] = prefixZeros[i] + (s[i] == '0');
}
for (int start = 0; start < n; start++) {
for (int end = start; end < n; end++) {
int ones = prefixOnes[end+1] - prefixOnes[start];
int zeros = prefixZeros[end+1] - prefixZeros[start];
if (ones >= zeros * zeros) count++;
}
}
return count;
}
int main() {
string s = "00011";
cout << dominantSubstrings(s) << endl; // Output: 5
return 0;
}function dominantSubstrings(s) {
const n = s.length;
const prefixOnes = new Array(n + 1).fill(0);
const prefixZeros = new Array(n + 1).fill(0);
let count = 0;
for (let i = 0; i < n; i++) {
prefixOnes[i + 1] = prefixOnes[i] + (s[i] === '1' ? 1 : 0);
prefixZeros[i + 1] = prefixZeros[i] + (s[i] === '0' ? 1 : 0);
}
for (let start = 0; start < n; start++) {
for (let end = start; end < n; end++) {
const ones = prefixOnes[end + 1] - prefixOnes[start];
const zeros = prefixZeros[end + 1] - prefixZeros[start];
if (ones >= zeros ** 2) count++;
}
}
return count;
}
const s = "101101";
console.log(dominantSubstrings(s)); // Output: 16#include <stdio.h>
#include <string.h>
int dominantSubstrings(char* s) {
int count = 0, n = strlen(s);
int prefixOnes[40001] = {0};
int prefixZeros[40001] = {0};
for (int i = 0; i < n; i++) {
prefixOnes[i+1] = prefixOnes[i] + (s[i] == '1');
prefixZeros[i+1] = prefixZeros[i] + (s[i] == '0');
}
for (int start = 0; start < n; start++) {
for (int end = start; end < n; end++) {
int ones = prefixOnes[end+1] - prefixOnes[start];
int zeros = prefixZeros[end+1] - prefixZeros[start];
if (ones >= zeros * zeros) count++;
}
}
return count;
}
int main() {
char s[] = "101101";
printf("%d\n", dominantSubstrings(s)); // Output: 16
return 0;
}using System;
class Program {
static int DominantSubstrings(string s) {
int n = s.Length, count = 0;
int[] prefixOnes = new int[n + 1];
int[] prefixZeros = new int[n + 1];
for (int i = 0; i < n; i++) {
prefixOnes[i + 1] = prefixOnes[i] + (s[i] == '1' ? 1 : 0);
prefixZeros[i + 1] = prefixZeros[i] + (s[i] == '0' ? 1 : 0);
}
for (int start = 0; start < n; start++) {
for (int end = start; end < n; end++) {
int ones = prefixOnes[end + 1] - prefixOnes[start];
int zeros = prefixZeros[end + 1] - prefixZeros[start];
if (ones >= zeros * zeros) count++;
}
}
return count;
}
static void Main() {
string s = "00011";
Console.WriteLine(DominantSubstrings(s)); // Output: 5
}
}The Python function uses precomputed lists of ones and zeros counts to quickly check the dominance of substrings, leveraging prefix sums for efficiency.
Time Complexity: O(n^2), achieved through optimized prefix sum usage.
Space Complexity: O(n) for prefix arrays.
Approach 3: Preprocessing + Enumeration
According to the problem description, a dominant string satisfies cnt_1 geq cnt_0^2, which means the maximum value of cnt_0 does not exceed \sqrt{n}, where n is the length of the string. Therefore, we can enumerate the value of cnt_0 and then calculate the number of substrings that satisfy the condition.
We first preprocess the position of the first 0 starting from each position in the string, storing it in the array nxt, where nxt[i] represents the position of the first 0 starting from position i, or n if it doesn't exist.
Next, we iterate through each position i in the string as the starting position of the substring, initializing cnt_0 to 0 or 1 (depending on whether the current position is 0). Then we use a pointer j starting from position i, jumping step by step to the position of the next 0, while updating the value of cnt_0.
For a substring starting at position i and containing cnt_0 zeros, it can contain at most nxt[j + 1] - i - cnt_0 ones. If this quantity is greater than or equal to cnt_0^2, it means there exists a substring that satisfies the condition. At this point, we need to determine how many positions the right endpoint nxt[j + 1] - 1 can move left while still satisfying the condition. Specifically, the right endpoint has a total of min(nxt[j + 1] - j, cnt_1 - cnt_0^2 + 1) possible choices. We accumulate these counts to the answer. Then we move pointer j to the position of the next 0 and continue enumerating the next value of cnt_0 until cnt_0^2 exceeds the string length.
The time complexity is O(n times \sqrt{n}), and the space complexity is O(n), where n is the length of the string.
function numberOfSubstrings(s: string): number {
const n = s.length;
const nxt: number[] = Array(n + 1).fill(0);
nxt[n] = n;
for (let i = n - 1; i >= 0; --i) {
nxt[i] = nxt[i + 1];
if (s[i] === '0') {
nxt[i] = i;
}
}
let ans = 0;
for (let i = 0; i < n; ++i) {
let cnt0 = s[i] === '0' ? 1 : 0;
let j = i;
while (j < n && cnt0 * cnt0 <= n) {
const cnt1 = nxt[j + 1] - i - cnt0;
if (cnt1 >= cnt0 * cnt0) {
ans += Math.min(nxt[j + 1] - j, cnt1 - cnt0 * cnt0 + 1);
}
j = nxt[j + 1];
++cnt0;
}
}
return ans;
}func numberOfSubstrings(s string) int {
n := len(s)
nxt := make([]int, n+1)
nxt[n] = n
for i := n - 1; i >= 0; i-- {
nxt[i] = nxt[i+1]
if s[i] == '0' {
nxt[i] = i
}
}
ans := 0
for i := 0; i < n; i++ {
cnt0 := 0
if s[i] == '0' {
cnt0 = 1
}
j := i
for j < n && int64(cnt0*cnt0) <= int64(n) {
cnt1 := nxt[j+1] - i - cnt0
if cnt1 >= cnt0*cnt0 {
ans += min(nxt[j+1]-j, cnt1-cnt0*cnt0+1)
}
j = nxt[j+1]
cnt0++
}
}
return ans
}impl Solution {
pub fn number_of_substrings(s: String) -> i32 {
let n = s.len();
let mut nxt = vec![n; n + 1];
for i in (0..n).rev() {
nxt[i] = nxt[i + 1];
if &s[i..i + 1] == "0" {
nxt[i] = i;
}
}
let mut ans = 0;
for i in 0..n {
let mut cnt0 = if &s[i..i + 1] == "0" { 1 } else { 0 };
let mut j = i;
while j < n && (cnt0 * cnt0) as i64 <= n as i64 {
let cnt1 = nxt[j + 1] - i - cnt0;
if cnt1 >= (cnt0 * cnt0) {
ans += std::cmp::min(nxt[j + 1] - j, cnt1 - cnt0 * cnt0 + 1);
}
j = nxt[j + 1];
cnt0 += 1;
}
}
ans as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3), considering three levels of loops. Space Complexity: O(1), since no extra space is used except for counting variables. |
| Optimized Approach with Prefix Sum | Time Complexity: O(n^2), achieved through optimized prefix sum usage. Space Complexity: O(n) for prefix arrays. |
| Preprocessing + Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n²) | O(1) | Good for understanding the condition and verifying correctness on small inputs |
| Enumeration with Prefix Sum | O(n√n) | O(n) | Efficient general solution using bounded zero count and fast substring queries |
Frequently asked questions
Is Count the Number of Substrings With Dominant Ones easy or hard?
The problem is rated Medium because the brute force idea is simple but the optimization requires recognizing the mathematical bound on zeros. Understanding how the condition ones ≥ zeros² limits substring structure is the key step that leads to an efficient solution.
Count the Number of Substrings With Dominant Ones Python/Java solution
Implementations typically compute a prefix sum array for ones, then enumerate substrings while tracking the number of zeros. The same logic works across Python, Java, C++, and C#, with time complexity around O(n√n) and O(n) auxiliary space.
How to solve Count the Number of Substrings With Dominant Ones in O(n)?
A strict O(n) solution is generally not used for this problem because the dominant condition depends on both substring length and zero count. Most optimized implementations rely on limiting the number of zeros to √n and using prefix sums to check the ones count quickly, which leads to O(n√n) time complexity.
What is the best approach for Count the Number of Substrings With Dominant Ones?
The most practical approach uses enumeration with prefix sums. The key observation is that if a substring has k zeros, it must contain at least k² ones, which limits k to about √n for a string of length n. By precomputing prefix sums of ones and only exploring substrings with small zero counts, the algorithm runs in roughly O(n√n) time.
Is Count the Number of Substrings With Dominant Ones asked at Google/Amazon/Meta?
Substring counting problems with mathematical constraints appear frequently in interviews at companies like Google, Amazon, and Meta. Variants that combine prefix sums, sliding window techniques, and enumeration logic are especially common in medium‑level interview rounds.
What data structure is used in Count the Number of Substrings With Dominant Ones?
The optimized solution primarily uses prefix sum arrays to quickly compute the number of ones in any substring. Combined with enumeration or sliding window logic, this allows constant‑time validation of the dominant ones condition while scanning the string.
What is the time complexity of Count the Number of Substrings With Dominant Ones?
The brute force solution checks every substring and runs in O(n²) time. The optimized approach reduces the search space by bounding the number of zeros and uses prefix sums for constant‑time range queries, resulting in about O(n√n) time and O(n) space.