<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)  # Length of the binary string
        
        # Calculate the maximum number of zeros to consider in any substring.
        # Since the condition is ones >= zeros^2, and the length of the string is N,
        # the maximum number of zeros z satisfies z^2 + z <= N.
        max_zeros = int(N ** 0.5) + 1  # Adding 1 to handle edge cases
        
        # Collect all indices where the character is '0'.
        zero_positions = [index for index, char in enumerate(S) if char == '0']
        zero_positions.append(N)  # Sentinel to handle the end of the string gracefully
        
        total_valid_substrings = 0  # Initialize the count of valid substrings
        total_zeros = len(zero_positions)  # Total number of zeros in the string
        current_zero_ptr = 0  # Pointer to track the first zero >= current starting index
        
        # Iterate over each possible starting index of the substring
        for start in range(N):
            # Move the zero pointer to the first zero that is >= the current start index
            while current_zero_ptr < total_zeros and zero_positions[current_zero_ptr] < start:
                current_zero_ptr += 1
            
            previous_zero_position = start  # Initialize the previous zero position to the start
            
            # Iterate over the number of zeros to include in the substring (from 0 up to max_zeros)
            for zero_count in range(max_zeros):
                target_zero_ptr = current_zero_ptr + zero_count  # Pointer to the current zero
                
                if target_zero_ptr >= total_zeros:
                    # No more zeros to consider
                    break
                
                current_zero_position = zero_positions[target_zero_ptr]  # Current zero's index
                
                # Calculate the minimum required length for the substring
                # to satisfy the condition: ones >= zeros^2
                # Since ones = length - zeros, the condition becomes:
                # length - zeros >= zeros^2 => length >= zeros^2 + zeros
                required_min_length = zero_count ** 2 + zero_count
                
                # Additionally, the substring must cover up to the previous zero position
                # to ensure it includes all zeros counted so far
                required_min_length = max(previous_zero_position - start + 1, required_min_length)
                
                # The maximum possible length is up to (but not including) the current zero position
                # This ensures the substring contains exactly 'zero_count' zeros
                max_possible_length = current_zero_position - start
                
                # Calculate the number of valid substrings for this zero_count
                # It is the number of lengths L such that:
                # required_min_length <= L <= max_possible_length
                valid_length_count = max_possible_length - required_min_length + 1
                
                if valid_length_count > 0:
                    # If there's at least one valid length, add to the total count
                    total_valid_substrings += valid_length_count
                
                # Update the previous zero position for the next iteration
                previous_zero_position = current_zero_position
        
        return total_valid_substrings

18200