<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:
        res = 0
        # find all consec 1s
        ocnt = 0
        onesofar = 0
        n = len(s)
        for c in s:
            if c == "0":
                onesofar = 0
            else:
                onesofar += 1
                ocnt += 1
            res += onesofar
        # sliding window
        zeroInds = [-1]
        for i, c in enumerate(s):
            if c == "0":
                zeroInds.append(i)
        zeroInds.append(n)
        print(zeroInds)

        maxZeros = floor(sqrt(ocnt))

        def helper(left, right, lo):
            if lo > left + right:
                return 0
            if left + right == lo:
                return 1
            if lo <= 0:
                return (left + 1) * (right + 1)
            if left == 0:
                return right - lo + 1
            if right == 0:
                return left - lo + 1
            res = 0
            for i in range(max(0, lo - right), left + 1):
                rneeded = max(0, lo - i)
                res += right - rneeded + 1
            return res

        for i in range(1, len(zeroInds) - 1):
            onesofar = 0  # in between ones
            left, right = (
                zeroInds[i] - zeroInds[i - 1] - 1,
                zeroInds[i + 1] - zeroInds[i] - 1,
            )
            if (left + right) >= 1:
                res += helper(left, right, 1)

            for j in range(i + 1, len(zeroInds) - 1):
                if (j - i + 1) > maxZeros:
                    break
                onesofar += zeroInds[j] - zeroInds[j - 1] - 1
                right = zeroInds[j + 1] - zeroInds[j] - 1
                if (left + right + onesofar) >= (j - i + 1) ** 2:
                    res += helper(left, right, (j - i + 1) ** 2 - onesofar)

        return res

19200