Skip to content

3479. Count The Number Of Substrings With Dominant Ones

String Sliding Window Enumeration

Problem - Count The Number Of Substrings With Dominant Ones

Medium

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'.

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        n = len(s)
        next_val = [n] * (n + 1)
        result = 0
        for i in range(n - 1, -1, -1):
            next_val[i] = next_val[i + 1]
            if s[i] == "0":
                next_val[i] = i

        for i in range(n):
            count_zeros = int(s[i] == "0")
            j = i
            while j < n and count_zeros**2 <= n:
                count_ones = (next_val[j + 1] - i) - count_zeros
                if count_ones >= count_zeros**2:
                    result += min(next_val[j + 1] - j, count_ones - count_zeros**2 + 1)
                j = next_val[j + 1]
                count_zeros += 1

        return result

Submission Stats:

  • Runtime: 10523 ms (55.17%)
  • Memory: 19.3 MB (44.83%)