<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:
        N = len(s)
        zeros = [i for i, x in enumerate(s) if x == '0']
        arr = [1 if x == '1' else 0 for x in s]
        psum = [0] + list(accumulate(arr))

        def actualSolver(a, b, x):
            d = x - b - 1
            if a < d :
                return 0
            h = a - d
            return (b+1)*(d+1) + (x-a+b)*(h)//2
        
        def ways(a, b, x):
            if a+b < x:
                return 0
        
            s = (a+1)*(b+1)
            if b < a:
                a,b = b,a
            if x < a:
                a = x - 1
                b = a
            elif x < b:
                b = x - 1
            return s - actualSolver(a, b, x)

        def solve(z):
            ans = 0
            for i in range(len(zeros)):
                l = i
                r = i+z-1
                if r >= len(zeros):
                    continue
                left = zeros[l]-(zeros[l-1] if l-1 >= 0 else -1)-1
                right = (zeros[r+1] if r+1 < len(zeros) else N)-zeros[r]-1
                curr = psum[zeros[r]+1]-psum[zeros[l]]
                need = max(0, (z**2) - curr)
                # print(l, r, left, right, need, int(ways_c(left, right, need)))
                ans += int(ways(left, right, need))
            return ans

        ans = 0

        for k, g in groupby(s):
            if k == '0':
                continue
            n = len(list(g))
            ans += (n*(n+1)) // 2
        # print(ans)
        for z in range(1, len(s)):
            if z + (z**2) > len(s):
                return ans
            # print(z, solve(z)) 
            ans += solve(z)

        return ans
            
        
19900