Watch 10 video solutions for Count the Number of Substrings With Dominant Ones, a medium level problem involving String, Sliding Window, Enumeration. This walkthrough by codestorywithMIK has 11,549 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 * 104s consists only of characters '0' and '1'.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 | 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 |