<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 SolutionX:
    def numberOfSubstrings(self, s: str) -> int:
        

        prefixSum = defaultdict(int, {-1:0})

        # This is to get no. of ones and zeros in a range.
        SUM = 0  
        for i, num in enumerate(s):
            SUM += int(num)
            prefixSum[i] += SUM

        
        ans = 0
        for i, num in enumerate(s):

            j = i # This loop doesn't run in O(N), this is eith log(n) or underroot(N)
            while j < len(s):

                ONES = prefixSum[j] - prefixSum[i-1]
                ZEROS = (j-i+1) - ONES

                # Happy path, dominant!
                if ZEROS * ZEROS <= ONES:
                    ans += 1
                    howMuchThisCanPushJ = int(ONES**0.5-(ZEROS)) # so to avoid stupid iteration in array where we HAPPY, JUMP "j" and add HAPPY jump to ans : )
                    nextj = j + howMuchThisCanPushJ
                    if nextj >= len(s) : ans += (len(s)-j-1)
                    else: ans += howMuchThisCanPushJ
                    j = nextj
                
                # Unhappy, non-dominent, so to avoid stupid iterations, JUMP "j"
                else:
                    howMuchThisCanPushJ = ( ZEROS * ZEROS) - ONES - 1
                    j += howMuchThisCanPushJ
                    
                
                j += 1
        
        return ans 
            

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        ans = 0 
        vals = [-1]
        for i, ch in enumerate(s): 
            one = zero = 0
            if ch == '1': one += 1
            else: zero += 1
            p = i 
            for v in reversed(vals): 
                one += p-v-1
                ans += max(0, min(p-v, one-zero**2+1))
                p = v 
                zero += 1
                if zero**2 > i: break 
            if ch == '0': vals.append(i)
        return ans 




        
18600