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

        res=0
        #to handle string with leading 1s
        zeros=[-1]

        for i, ch in enumerate(s):
            one=zero=0
            if ch=="1":
                one=1
            else:
                zero=1
            prev=i
            for v in reversed(zeros):
                one+=prev-v-1
                print(f"i:{i} p-v:{prev-v} o:{one} x:{one-zero**2+1} r:{res}")
                res+=max(0, min(prev-v, one-zero**2+1))

                prev=v
                zero+=1
                if zero**2>i:
                    break
            if ch=="0":
                zeros.append(i)

        return res
        
class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        ans = 0 
        for z in range(isqrt(len(s))+1): 
            j = zeroj = 0 
            k = zerok = onek = 0 
            for i, ch in enumerate(s): 
                if ch == '0': zeroj += 1; zerok += 1
                else: onek += 1
                while zeroj > z: 
                    if s[j] == '0': zeroj -= 1
                    j += 1
                while zerok > z or k <= i and zerok == z and onek >= zerok**2: 
                    if s[k] == '0': zerok -= 1
                    else: onek -= 1
                    k += 1
                ans += k-j
        return ans 
        
class Solution2:
    def numberOfSubstrings(self, s: str) -> int:
        """
        https://leetcode.com/problems/count-the-number-of-substrings-with-dominant-ones/solutions/5548547/well-explained-very-easy-java/

        We calculate the prefix Sums of ones first.
Whenever we get a substring which is either dominant or not. We move forward to make it the opposite.
For ex :- If ones=10, zeros=2, then it is a dominant substring. But if in the next 2 positions we get zeros, then it will become a non-dominant substring. So we move up 2 positions ahead in hope of finding a non-dominant substring (starting position i is fixed, we move j) vice versa for if it is a non-dominant substring we found.

Whenever we find a dominant substring, we update our result. Though the solution is already provided, still posting mine. Thanks.
https://leetcode.com/problems/count-the-number-of-substrings-with-dominant-ones/solutions/5546415/easiest-solution-and-simple-understanding-of-the-question/comments/2543781
        """
        n = len(s)
        psum = list(accumulate([i=="1" for i in s], initial=0))

        res=0
        for i in range(n):
            j=i
            while j<n:
                ones = psum[j+1]-psum[i]
                zeros = j-i+1-ones

                if ones>=zeros**2:
                    res+=1

                    diff=isqrt(ones)-zeros
                    """
                    If this condition is satisfied (countcount <= one), then output should be increased by one, i.e., output++.
Now the optimization part until what index we can jump up to where (countcount <= 1) this condition remains intact. That is, to take the square root of one and decrease with the count of zero. The reason for this is that if we add that number of zero by moving right, then also this condition will remain true. One must ensure that we move that much right that lies in the boundary, which means s.length(). So if j is the current index and (kl-count) is the number of steps we are moving right, then the total should be less than s.length().
                    https://leetcode.com/problems/count-the-number-of-substrings-with-dominant-ones/solutions/5546415/easiest-solution-and-simple-understanding-of-the-question/comments/2544259

                    """
                    if diff>0:
                        res+= n-j-1 if j+diff>=n else diff
                    #  jump where zero can be greater than one.
                    j+=diff+1
                else:
                    # jump where next soltuion is possible
                    j+=zeros**2-ones

        return res

class Solution2:
    def numberOfSubstrings(self, s: str) -> int:
        n = len(s)
        result = 0
        
        # Iterate through possible zero counts (1 to sqrt(n))
        for k in range(1, int(n**0.5) + 1):
            zeros = deque()  # Queue to store positions of zeros
            lastzero = -1    # Position of the zero before the first zero in our window
            ones = 0         # Count of ones in our current window
            
            # Scan through the string
            for right in range(n):
                if s[right] == '0':
                    zeros.append(right)
                    # If we have more than k zeros, remove the leftmost one
                    while len(zeros) > k:
                        ones -= (zeros[0] - lastzero - 1)  # Subtract ones between lastzero and the removed zero
                        lastzero = zeros.popleft()
                else:
                    ones += 1
                
                # If we have exactly k zeros and at least k^2 ones
                if len(zeros) == k and ones >= k**2:
                    x=min(zeros[0] - lastzero, ones - k**2 + 1)
                    print(f"r:{right} k:{k} o:{ones} z0:{zeros[0]} lz:{lastzero} x:{x} r:{result}")
                    # Add the minimum of:
                    # 1. Number of ways to extend to the left (zeros[0] - lastzero)
                    # 2. Number of ways to extend to the right (ones - k**2 + 1)
                    result += min(zeros[0] - lastzero, ones - k**2 + 1)
        
        # Handle all-ones substrings
        i = 0
        while i < n:
            if s[i] == '0':
                i += 1
                continue
            sz = 0
            while i < n and s[i] == '1':
                sz += 1
                i += 1
            # Add number of all-ones substrings
            result += (sz * (sz + 1)) // 2
        
        return result
17100