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

from collections import deque
class Solution:
    # O(n^2), brute force,TLE
    def numberOfSubstrings(self, s: str) -> int:
        n = len(s)
        ans = 0
        for start in range(n):
            cnt0 = 0
            cnt1 = 0
            for end in range(start+1,n):
                if s[end] == '1':
                    cnt1 += 1
                else:
                    cnt0 += 1
                if cnt1>=cnt0*cnt0:
                    ans += 1
        return ans
    
    # O(n*(3/2)), sliding windows
    def numberOfSubstrings(self, s: str) -> int:
        # can not run sliding windows directly
        # subquestion: fix the number of 0, run sliding windows
        n = len(s)
        maxZero = 0
        while maxZero*maxZero+maxZero <= n:
            maxZero += 1

        ans = 0
        for zeroCnt in range(maxZero):
            zeroIndex = deque()
            left = 0
            curZeroCnt = 0
            minL = zeroCnt*zeroCnt+zeroCnt

            for right in range(n):
                if s[right] == '0':
                    curZeroCnt += 1
                    zeroIndex.append(right)
                while curZeroCnt > zeroCnt:
                    if s[left] == '0':
                        curZeroCnt -= 1
                        zeroIndex.popleft()
                    left += 1

                if curZeroCnt == zeroCnt and minL <= right-left+1:
                    leadingZeroIndex = right
                    if zeroIndex:
                        leadingZeroIndex = zeroIndex[0]
                    # how many leading 1 you can delete
                    # first, based on leadingZeroIndex
                    # also need to satisfy minL <= length
                    toIndex = min(leadingZeroIndex,right-minL+1)
                    ans += toIndex-left+1
            print(zeroCnt,ans)
        return ans


17000