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 NeetCode has 177,962 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'.