Copy of Copy of Copy of Template
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 * 104
s
consists only of characters'0'
and'1'
.
Intuition
Links
https://leetcode.com/problems/count-the-number-of-substrings-with-dominant-ones/
Video Links
https://www.youtube.com/watch?v=hcGvofpRBg0&t=1030s&ab_channel=AbhinavAwasthi
Approach 1:
Approach 2:
Approach 3:
Approach 4:
Similar Problems
Last updated