<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:
        n = len(s)
        
        # Step 1: Precompute prefix sums for '1's
        prefix1 = [0] * (n + 1)
        for i in range(n):
            prefix1[i + 1] = prefix1[i] + (s[i] == '1')
        
        # Step 2: Collect positions of '0's
        zeros_pos = [i for i, c in enumerate(s) if c == '0']
        num_zeros = len(zeros_pos)
        
        total = 0  # Total number of valid substrings
        
        # Step 3: Handle z = 0 (substrings with no '0's)
        # These are continuous runs of '1's
        count = 0
        for c in s:
            if c == '1':
                count += 1
            else:
                if count > 0:
                    total += count * (count + 1) // 2
                    count = 0
        # Add the last run if the string ends with '1's
        if count > 0:
            total += count * (count + 1) // 2
        
        # Step 4: Handle z >= 1
        # Maximum z is bounded by sqrt(n)
        import math
        z_max = int(math.isqrt(n)) + 1  # Adding 1 to include sqrt(n) if exact
        
        for z in range(1, z_max + 1):
            if z * z > n:
                break  # No substrings can satisfy '1's >= z^2 if z^2 > n
            if z > num_zeros:
                continue  # Not enough '0's in the string for this z
            
            # Iterate through all possible groups of exactly z zeros
            for i in range(num_zeros - z + 1):
                first_zero = zeros_pos[i]
                last_zero = zeros_pos[i + z - 1]
                
                # Determine the boundaries
                left_bound = zeros_pos[i - 1] + 1 if i > 0 else 0
                right_bound = zeros_pos[i + z] - 1 if (i + z) < num_zeros else n - 1
                
                # Number of ways to choose the start position
                left_options = first_zero - left_bound + 1
                # Number of ways to choose the end position
                right_options = right_bound - last_zero + 1
                
                # Now, for each possible start position within left_options,
                # determine the minimum end position to satisfy the condition
                # '1's >= z^2
                
                # To ensure '1's >= z^2,
                # the length of the substring should be >= z^2 + z
                # because number of '1's = length - z >= z^2
                min_length = z * z + z
                
                # Iterate through all possible start positions
                for start_offset in range(left_options):
                    start = left_bound + start_offset
                    # Calculate the minimum end index required
                    required_end = start + min_length - 1
                    # The end must at least cover the last zero
                    required_end = max(required_end, last_zero)
                    
                    if required_end > right_bound:
                        continue  # No valid end positions for this start
                    
                    # The number of valid end positions for this start
                    valid_ends = right_bound - required_end + 1
                    total += valid_ends
        
        return total

19100