<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 defaultdict
from bisect import bisect_left

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        ## For a particular index find the valid substring range i.e ..i....[k1,k2,k3...kn] 
        # First come up with the bruteforce n * n to n * root(n) or n * log(n) solutions here n * root(n) works
        
        # number of ones should be greater than or equal to the zeroes squared
        # let the number of ones be x and the number of zeroes be y
        # so x >= y * y or y * y >= x
        # we traverse back upto root(x)
        # the traversal is O(sqrt(x)) i.e., y <= sqrt(x)
        # so the problem can be solved in O(n * sqrt(n))
        
        # now fixed the i and choose 0,1,2,   root(n) zeroes either left or right (right choosing is tricky need to maintain the queue for that and it's easy to use using prev and curr)
        
        
        n = len(s)
        zeroes = deque(i for i, c in enumerate(s) if c=='0')
        ones = n - len(zeroes)
        # know that zeroes * zeroes <= ones
        limit = int(ones ** 0.5) + 1
        zeroes.append(n)
        res = 0

        for i in range(n):
            while zeroes and zeroes[0] < i:
                zeroes.popleft()
            
            curr = i
            for zeroCnt, nxt in enumerate(zeroes):
                if zeroCnt >= limit: 
                    break

                # curr and nxt are index of zeroes just think about range when 0 zeroes , 1 zeroes ...
                # 0 zeroes: below first 0 index after i i.e [i, first_zero_idx)
                # similarly for other so maintain curr and nxt
                # dealing with substring left=i, right in [curr, nxt)
                max_length = nxt-i  # [i, nxt)
                # remove the invalids from maxLnt 
                # let think i.............curr.......nxt.........
                # now       i.....0.......0..........nxt...........
                # i.e two zeroes till curr obviously need to remove at least upto curr i.e curr-i +1
                # but do we have sufficient ones to fulfill the choosed zeros i.e how much more need to go after curr such that two zeroes we have and have dominant ones
                # we have at that stage ones = curr-i+1 - zeroes
                # we know that invalid condition ones - zeroes*zeroes < 0
                # curr - i + 1 - (zeroes * zeroes + zeroes) < 0
                # curr - i + 1 < (zeroes * zeroes + zeroes)
                # so to remove that invalid condition we need to increase our curr until curr - i + 1 == zeroes * zeroes + zeroes after that it's >
                # i.e remove the invalids either it's will be curr - i + 1 if zeroes * zeroes + zeroes are lesser
                # else the invalids will be zeroes * zeroes + zero (as increment curr till dominant ones at that state curr - i + 1)
                min_length = max(curr-i+1, zeroCnt * zeroCnt + zeroCnt)
                res += max(0, max_length - min_length + 1)

                curr = nxt
        
        return res
        

18000