<p>You are given a binary string <code>s</code>.</p>

<p>Return the number of <span data-keyword="substring-nonempty">substrings</span> with <strong>dominant</strong> ones.</p>

<p>A string has <strong>dominant</strong> ones if the number of ones in the string is <strong>greater than or equal to</strong> the <strong>square</strong> of the number of zeros in the string.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;00011&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">5</span></p>

<p><strong>Explanation:</strong></p>

<p>The substrings with dominant ones are shown in the table below.</p>
</div>

<table>
	<thead>
		<tr>
			<th>i</th>
			<th>j</th>
			<th>s[i..j]</th>
			<th>Number of Zeros</th>
			<th>Number of Ones</th>
		</tr>
	</thead>
	<tbody>
		<tr>
			<td>3</td>
			<td>3</td>
			<td>1</td>
			<td>0</td>
			<td>1</td>
		</tr>
		<tr>
			<td>4</td>
			<td>4</td>
			<td>1</td>
			<td>0</td>
			<td>1</td>
		</tr>
		<tr>
			<td>2</td>
			<td>3</td>
			<td>01</td>
			<td>1</td>
			<td>1</td>
		</tr>
		<tr>
			<td>3</td>
			<td>4</td>
			<td>11</td>
			<td>0</td>
			<td>2</td>
		</tr>
		<tr>
			<td>2</td>
			<td>4</td>
			<td>011</td>
			<td>1</td>
			<td>2</td>
		</tr>
	</tbody>
</table>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;101101&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">16</span></p>

<p><strong>Explanation:</strong></p>

<p>The substrings with <strong>non-dominant</strong> ones are shown in the table below.</p>

<p>Since there are 21 substrings total and 5 of them have non-dominant ones, it follows that there are 16 substrings with dominant ones.</p>
</div>

<table>
	<thead>
		<tr>
			<th>i</th>
			<th>j</th>
			<th>s[i..j]</th>
			<th>Number of Zeros</th>
			<th>Number of Ones</th>
		</tr>
	</thead>
	<tbody>
		<tr>
			<td>1</td>
			<td>1</td>
			<td>0</td>
			<td>1</td>
			<td>0</td>
		</tr>
		<tr>
			<td>4</td>
			<td>4</td>
			<td>0</td>
			<td>1</td>
			<td>0</td>
		</tr>
		<tr>
			<td>1</td>
			<td>4</td>
			<td>0110</td>
			<td>2</td>
			<td>2</td>
		</tr>
		<tr>
			<td>0</td>
			<td>4</td>
			<td>10110</td>
			<td>2</td>
			<td>3</td>
		</tr>
		<tr>
			<td>1</td>
			<td>5</td>
			<td>01101</td>
			<td>2</td>
			<td>3</td>
		</tr>
	</tbody>
</table>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 4 * 10<sup>4</sup></code></li>
	<li><code>s</code> consists only of characters <code>&#39;0&#39;</code> and <code>&#39;1&#39;</code>.</li>
</ul>

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        # From votrubac's solution

        # key intuition: as zeroes grow, ones must grow quadratically
        # so there is a roughly sqrt(len(s)) upper limit on the number of
        # zeroes in a valid substring

        # use sliding windows with a number of zeroes in the range(0, len(s))
        # once this range hits a point where we stop seeing valid substrings 
        # we can exit early since adding more zeroes won't make more valid substrings

        # also while counting the numbers of substrings during 
        # extension of the window, we need to know the index (p) of the first
        # zero in the window since this tells us how many new
        # valid subtstrings we constructed:
        #   Consider this example when z == 2:
        #   110101: one substring
        #   1101011: +2 substrings (1101011 and 101011)
        #   11010111: +3 substrings (11010111, 1010111, and 010111)
        #   110101111: +3 substrings (110101111, 10101111, and 10101111)
        # Extending generates 1 + min(p - start, ones - zeroes**2) additional substrings
        # [ones - zeroes**2 checks for the number of excess ones we have]
        res, n = 0, len(s)
        for z in range(1 + int(sqrt(n))):
            zeroes, ones, p, l, found = 0, 0, 0, 0, False
            for r in range(n):
                if s[r] == "1": ones += 1
                else: zeroes += 1
                while zeroes > z:
                    if s[l] == "1": ones -= 1
                    else: zeroes -= 1
                    l += 1
                if zeroes == z and ones > 0 and ones >= z*z:
                    p = max(p, l)
                    while p < r and s[p] == "1": p += 1
                    res += 1 + min(p - l, ones - z*z)
                    found = True
            if not found: break
        return res
16500