Count the Number of Substrings With Dominant Ones - Solution & Explanation
Problem Statement
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.
This C function iterates through each possible substring of the input binary string s and counts the number of ones and zeros. It then checks if the substring has dominant ones by comparing the count of ones to the square of zeros.
Complexity
Time Complexity: O(n^3), where n is the length of the string due to nested iterations.
Space Complexity: O(1), as no additional space is utilized apart from 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.
This C implementation uses arrays to store accumulated counts of ones and zeros for each position. This allows for quick determination of ones and zeros in any substring.
Complexity
Time Complexity: O(n^2), with optimized substring evaluation using prefix sums.
Space Complexity: O(n), for storing prefix counts.
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.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3), where n is the length of the string due to nested iterations. Space Complexity: O(1), as no additional space is utilized apart from variables. |
| Optimized Approach with Prefix Sum | Time Complexity: O(n^2), with optimized substring evaluation using prefix sums. Space Complexity: O(n), for storing prefix counts. |
| Preprocessing + Enumeration | — |
Detailed 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 |
Video Solution
Count the Number of Substrings With Dominant Ones | Brute Force | Improved | Leetcode 3234 | MIK • codestorywithMIK • 12,230 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count the Number of Substrings With Dominant Ones easy or hard?
Count the Number of Substrings With Dominant Ones Python/Java solution
How to solve Count the Number of Substrings With Dominant Ones in O(n)?
What is the best approach for Count the Number of Substrings With Dominant Ones?
Is Count the Number of Substrings With Dominant Ones asked at Google/Amazon/Meta?
What data structure is used in Count the Number of Substrings With Dominant Ones?
What is the time complexity of Count the Number of Substrings With Dominant Ones?
Ready to solve this problem?
Practice Count the Number of Substrings With Dominant Ones with our built-in code editor and test cases.
Practice on FleetCode