<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:
        bstring = [int(c) for c in s]
        prefix = list(accumulate(bstring, initial=0))
        right_ones = [0 for _ in range(len(s))]
        left_ones = [0 for _ in range(len(s))]
        for idx in reversed(range(len(s))):
            if idx == len(s) - 1: left_ones[idx] = int(s[idx])
            elif s[idx] == '0': left_ones[idx] = 0
            else: left_ones[idx] = 1 + left_ones[idx + 1]
        
        for idx in range(len(s)):
            if idx == 0: right_ones[idx] = int(s[idx])
            elif s[idx] == '0': right_ones[idx] = 0
            else: right_ones[idx] = 1 + right_ones[idx - 1]
        
        zt = 0
        for k, g in groupby(bstring):
            if k == 0: continue
            l = len(list(g))
            zt += ((l) * (l + 1)) // 2

        def zero_count(zero_size):
            stack = []
            next_idx = [-1 for _ in range(len(s))]
            for idx in reversed(range(len(s))):
                if s[idx] == '1': continue
                if len(stack) == zero_size: 
                    stack.pop()
                stack.insert(0, idx)
                if len(stack) == zero_size:
                    next_idx[idx] = stack[-1]
            total = 0
            for idx in reversed(range(len(s))):
                if s[idx] == '1': continue
                if next_idx[idx] == -1: continue
                left, right = idx, next_idx[idx] + 1
                middle_ones = prefix[right] - prefix[left]
                remaining_ones_l = left_ones[right] if right < len(s) else 0
                remaining_ones_r = right_ones[left - 1] if left > 0 else 0
                goal_ones = zero_size ** 2
                all_ones = middle_ones + remaining_ones_r + remaining_ones_l
                if all_ones < goal_ones: continue

                if middle_ones >= goal_ones:
                    total += (remaining_ones_r + 1) * (remaining_ones_l + 1)
                else:
                    for used in reversed(range(remaining_ones_r + 1)):
                        if middle_ones + used + remaining_ones_l < goal_ones: continue
                        if middle_ones + used >= goal_ones:
                            total += remaining_ones_l + 1
                        else:
                            total += remaining_ones_l - (goal_ones - middle_ones - used) + 1
            return total
        
        total = 0
        for sz in range(1, len(s)):
            if (sz ** 2) + sz > len(s): break
            total += zero_count(sz)

        return total + zt
22400