# Count the Number of Substrings With Dominant Ones **Difficulty:** MEDIUM [External](https://leetcode.com/problems/count-the-number-of-substrings-with-dominant-ones) Canonical: https://scaleengineer.com/dsa/problems/count-the-number-of-substrings-with-dominant-ones **Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration) **Data structures:** String --- ## 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 * 104` * `s` consists only of characters `'0'` and `'1'`. # Approaches ## Brute Force Enumeration of Substrings The most straightforward approach is to generate every possible substring of the input string `s`, and for each substring, check if it satisfies the 'dominant ones' condition. A substring is dominant if the count of '1's is greater than or equal to the square of the count of '0's. **Time:** O(N^2), where N is the length of the string `s`. The two nested loops iterate through all possible substrings, which are O(N^2) in number. For each substring, the check is an O(1) operation. · **Space:** O(1), as we only use a few variables to store the counts and the final answer, regardless of the input string size. **Pros:** Simple to understand and implement. **Cons:** Inefficient for large inputs. Given N can be up to 4 * 10^4, N^2 can be up to 1.6 * 10^9, which will lead to a Time Limit Exceeded (TLE) error. ### Explanation We can use two nested loops to define all substrings. The outer loop iterates through all possible starting indices `i` from `0` to `n-1`, and the inner loop iterates through all possible ending indices `j` from `i` to `n-1`, where `n` is the length of the string. For each substring `s[i..j]`, we can maintain a running count of zeros (`zeros`) and ones (`ones`). As we extend the substring by moving `j` from `i` to `n-1`, we update these counts. After each update, we check if the condition `ones >= zeros * zeros` holds. If it does, we increment our total count of dominant substrings. Here is the algorithm: 1. Initialize a counter `ans` to 0. 2. Loop for `i` from `0` to `n-1`: a. Initialize `zeros = 0` and `ones = 0`. b. Loop for `j` from `i` to `n-1`: i. If `s[j]` is '0', increment `zeros`. Otherwise, increment `ones`. ii. Check if `ones >= zeros * zeros`. iii. If the condition is true, increment `ans`. 3. Return `ans`. ```java class Solution { public long countSubstrings(String s) { int n = s.length(); long ans = 0; for (int i = 0; i < n; i++) { int zeros = 0; int ones = 0; for (int j = i; j < n; j++) { if (s.charAt(j) == '0') { zeros++; } else { ones++; } if (ones >= (long)zeros * zeros) { ans++; } } } return ans; } } ``` ### Algorithm 1. Initialize a variable `ans` to 0 to store the count of dominant substrings. 2. Use a nested loop to iterate through all possible substrings. The outer loop variable `i` represents the start of the substring, and the inner loop variable `j` represents the end. 3. For each starting index `i`, initialize counts for zeros and ones to 0. 4. In the inner loop, for each character `s[j]`, update the counts of zeros and ones for the substring `s[i..j]`. 5. Check if the condition `ones >= zeros * zeros` is met. 6. If the condition is true, increment `ans`. 7. After iterating through all substrings, return `ans`. ## Optimized Iteration by Bounding Zeros A key observation is that the number of zeros (`c0`) in a dominant substring cannot be very large. The condition is `c1 >= c0 * c0`. Since the number of ones `c1` is at most the length of the string `N`, we must have `N >= c1 >= c0 * c0`, which implies `c0 <= sqrt(N)`. This insight allows us to design a more efficient algorithm by limiting our search based on the number of zeros. Instead of a simple nested loop, we can iterate through each possible starting position `i` and then, for each `i`, count the valid substrings based on the number of zeros they contain. **Time:** O(N * sqrt(N)), where N is the length of the string. The outer loop runs N times. The inner loop over `c0` runs at most `sqrt(N)` times. All operations inside the inner loop take O(1) time (assuming pre-computation). The pre-computation of zero indices takes O(N). · **Space:** O(Z), where Z is the number of zeros in the string, to store `zeroIndices`. In the worst case, Z can be N, so the space complexity is O(N). **Pros:** Significantly more efficient than the brute-force approach.; Passes the time limits for the given constraints. **Cons:** More complex to reason about and implement correctly compared to the brute-force solution. ### Explanation The algorithm iterates through each index `i` as a potential start of a substring. For each `i`, we calculate the number of dominant substrings starting at `i`. We can handle two cases for the number of zeros (`c0`) in a substring `s[i..j]`: 1. **`c0 = 0`**: The substring contains only '1's. The condition `c1 >= 0*0` is always true for non-empty substrings. We can find the next occurrence of '0' after `i` (or the end of the string) and add all substrings `s[i..j]` within this range to the count. 2. **`c0 > 0`**: We can iterate through the possible number of zeros, `c0`, from 1 up to `sqrt(N)`. For a fixed `i` and `c0`, we can determine the exact range of ending indices `j` for which the substring `s[i..j]` contains exactly `c0` zeros. This range is defined by the positions of the `c0`-th and `(c0+1)`-th zeros after index `i`. Within this range of `j`, we apply the dominance condition `c1 >= c0*c0`, which simplifies to a condition on `j`: `j >= i + c0*c0 + c0 - 1`. We can then count how many integers `j` fall into the intersection of these two ranges in O(1) time. To efficiently find the positions of zeros, we can pre-process the string and store the indices of all zeros in a list. Here is the algorithm: 1. Pre-compute a list `zeroIndices` containing the indices of all '0's in `s`. 2. Initialize `ans = 0`. 3. Iterate `i` from `0` to `n-1`: a. Find the index `zeroPtr` of the first zero in `zeroIndices` that is at or after `i`. b. **Case `c0 = 0`**: All substrings starting at `i` and ending before the zero at `zeroIndices[zeroPtr]` are dominant. Add their count to `ans`. c. **Case `c0 > 0`**: Loop `c0` from 1 as long as `c0*c0 <= n`. i. Determine the range of `j` where `s[i..j]` has exactly `c0` zeros. This is from the `c0`-th zero after `i` up to the character before the `(c0+1)`-th zero. ii. Calculate the minimum `j` required by the dominance condition: `minJ = i + c0*c0 + c0 - 1`. iii. Find the number of `j`'s that satisfy both conditions and add this to `ans`. 4. Return `ans`. ```java import java.util.ArrayList; import java.util.List; class Solution { public long countSubstrings(String s) { int n = s.length(); long count = 0; List zeroIndices = new ArrayList<>(); for (int i = 0; i < n; i++) { if (s.charAt(i) == '0') { zeroIndices.add(i); } } int numZeros = zeroIndices.size(); int zeroPtr = 0; for (int i = 0; i < n; i++) { // Find the first zero at or after index i while (zeroPtr < numZeros && zeroIndices.get(zeroPtr) < i) { zeroPtr++; } // Case 1: Substrings with c0 = 0 zeros int nextZeroPos = (zeroPtr < numZeros) ? zeroIndices.get(zeroPtr) : n; // All substrings s[i...j] where j is in [i, nextZeroPos - 1] have 0 zeros. // They are all dominant. There are (nextZeroPos - i) such substrings. count += (nextZeroPos - i); // Case 2: Substrings with c0 > 0 zeros for (int c0 = 1; (long)c0 * c0 <= n; c0++) { int currentZeroGroupIdx = zeroPtr + c0 - 1; if (currentZeroGroupIdx >= numZeros) { break; // Not enough zeros left in the string } // A substring s[i..j] with c0 zeros must end at or after the c0-th zero from i // and before the (c0+1)-th zero. int startJRange = zeroIndices.get(currentZeroGroupIdx); int endJRange = (currentZeroGroupIdx + 1 < numZeros) ? zeroIndices.get(currentZeroGroupIdx + 1) - 1 : n - 1; // Dominance condition: c1 >= c0*c0 => (j-i+1) - c0 >= c0*c0 // => j >= i + c0*c0 + c0 - 1 long minJ = (long)i + (long)c0 * c0 + (long)c0 - 1; long validStartJ = Math.max(startJRange, minJ); long validEndJ = endJRange; if (validStartJ <= validEndJ) { count += (validEndJ - validStartJ + 1); } } } return count; } } ``` ### Algorithm 1. Pre-process the string to get a list of all indices where '0' appears. Let's call it `zeroIndices`. 2. Initialize a total count `ans` to 0. 3. Iterate through the string with an index `i` from 0 to `n-1`, representing the start of a substring. 4. For each `i`, find the index `zeroPtr` in `zeroIndices` corresponding to the first '0' at or after `i`. 5. First, count substrings with zero '0's. These are substrings starting at `i` and ending before the '0' at `zeroIndices[zeroPtr]`. All such non-empty substrings are dominant. Add their count to `ans`. 6. Then, iterate for the number of zeros `c0` from 1 up to `sqrt(n)`. We can stop at `sqrt(n)` because if `c0 > sqrt(n)`, then `c0*c0 > n`, making the condition `c1 >= c0*c0` impossible to satisfy as `c1 <= n`. 7. For each `c0`, determine the range of ending indices `j` such that `s[i..j]` has exactly `c0` zeros. This range is bounded by the `c0`-th and `(c0+1)`-th zeros from `zeroPtr`. 8. Calculate the minimum `j` required by the dominance condition: `j >= i + c0*c0 + c0 - 1`. 9. The number of valid substrings for this `i` and `c0` is the size of the intersection of the two ranges for `j`. Add this number to `ans`. 10. Return `ans` after the outer loop finishes.