Leetcode 3234. Count the Number of Substrings With Dominant Ones

Let's understand what we're being asked to do. We have a binary string like s = "110100" (containing only '0' and '1' characters) and need to count how many substrings satisfy a special condition: the number of '1's must be at least the square of the number of '0's.

Let's trace through a small example with s = "101". Consider substring "101": it has 2 ones and 1 zero. Is 2 >= 1^2? Yes! (2 >= 1). So this substring qualifies. Now consider "10": it has 1 one and 1 zero. Is 1 >= 1^2? Yes! (1 >= 1). Consider "01": it has 1 one and 1 zero. Is 1 >= 1^2? Yes! Single character substrings "1" have 1 one and 0 zeros: is 1 >= 0^2? Yes! (1 >= 0).

Key constraint: The string length can be up to 4×10^4 (40,000 characters). A naive approach checking all possible substrings would be too slow.

Important observation: The condition ones >= zeros^2 means that as the number of zeros grows, we need exponentially more ones. For example, if zeros = 10, we'd need ones >= 100. If zeros = 200, we'd need ones >= 40,000. This means qualifying substrings can't have too many zeros - at most around O(√n) zeros!

Edge cases: What if the string is all '1's? (every substring qualifies). What if it's all '0's? (only single '0' substrings might qualify if 0 >= 1, which is false, so none qualify except... wait, does 0 >= 0^2 hold? Yes! So single '0' counts).

The brute force approach checks every possible substring: use two nested loops where the outer loop picks the starting index and the inner loop extends to each possible ending index. For each substring, count the number of ones and zeros, then check if the condition ones >= zeros^2 holds. If it does, increment the result counter. This approach is straightforward but inefficient because it examines all O(n^2) substrings and counts characters for each one.

def count_qualifying_substrings(s):
    """
    Brute force: Check all O(n^2) substrings.
    For each substring, count ones and zeros, then verify ones >= zeros^2.
    """
    n = len(s)
    count = 0
    
    # Outer loop: pick starting index
    for start in range(n):
        ones = 0
        zeros = 0
        
        # Inner loop: extend to each ending index
        for end in range(start, n):
            # Count current character
            if s[end] == '1':
                ones += 1
            else:
                zeros += 1
            
            # Check if condition holds: ones >= zeros^2
            if ones >= zeros * zeros:
                count += 1
    
    return count

The condition ones >= zeros^2 creates a powerful constraint: as zeros increase, the required ones grow quadratically.

For a string of length n = 40,000, if a substring has zeros = 200, it needs ones >= 40,000. But the entire string is only 40,000 characters! This means any qualifying substring can have at most around √n zeros (roughly 200 zeros for n = 40,000).

This observation is the key: instead of checking all O(n^2) substrings, we can enumerate by the number of zeros (only O(√n) possible values), and for each zero-count, efficiently count qualifying substrings.

By fixing the number of zeros k (where k ranges from 0 to roughly √n), we transform the problem:

For each fixed k: Find all substrings with exactly k zeros where ones >= k^2.

This means we need substrings with exactly k zeros and at least k^2 ones. We can use a sliding window or two-pointer technique to efficiently count these substrings for each k.

Total complexity: O(√n) values of k, and for each k, we scan the string in O(n) time → O(n√n) total, which is fast enough!

Imagine you're counting valid substrings, but you organize your work by how many zeros each substring contains:

• Bucket 0: Substrings with 0 zeros (all '1's). Condition: ones >= 0^2 = 0. Every substring of consecutive '1's qualifies!
• Bucket 1: Substrings with exactly 1 zero. Condition: ones >= 1^2 = 1. Need at least 1 one.
• Bucket 2: Substrings with exactly 2 zeros. Condition: ones >= 2^2 = 4. Need at least 4 ones.
• Bucket k: Substrings with exactly k zeros. Condition: ones >= k^2.

For each bucket, you can use a window-based counting technique: expand a window to include exactly k zeros, then count how many valid substrings exist within that window (those with enough ones).

The magic is that you only need to process O(√n) buckets, making the solution efficient!

The optimal approach leverages the key observation that qualifying substrings can have at most O(√n) zeros. We enumerate by the number of zeros: for each possible zero-count k from 0 to √n, we find all substrings with exactly k zeros and at least k^2 ones. For each fixed k, we use a sliding window or two-pointer technique to efficiently count valid substrings. We maintain a window that contains exactly k zeros, then count how many ways we can choose substrings within or around this window that satisfy the ones requirement. By summing counts across all k values, we get the total answer in O(n√n) time.

def count_qualifying_substrings(s):
    """
    Count substrings where ones >= zeros^2.
    Key insight: qualifying substrings have at most sqrt(n) zeros.
    """
    n = len(s)
    total_count = 0
    max_zeros = int(n ** 0.5) + 1
    
    # Enumerate by number of zeros
    for k in range(max_zeros + 1):
        # Find all substrings with exactly k zeros
        # For each such substring, check if ones >= k^2
        
        if k == 0:
            # Special case: no zeros, count all-ones substrings
            i = 0
            while i < n:
                if s[i] == '1':
                    # Count consecutive ones
                    j = i
                    while j < n and s[j] == '1':
                        j += 1
                    length = j - i
                    # All substrings of consecutive ones qualify
                    total_count += length * (length + 1) // 2
                    i = j
                else:
                    i += 1
        else:
            # Use sliding window to find substrings with exactly k zeros
            zero_positions = [-1]
            for i in range(n):
                if s[i] == '0':
                    zero_positions.append(i)
            zero_positions.append(n)
            
            # For each window with exactly k zeros
            for i in range(len(zero_positions) - k - 1):
                # Window boundaries: after zero_positions[i] to before zero_positions[i+k+1]
                left_boundary = zero_positions[i]
                right_boundary = zero_positions[i + k + 1]
                
                # The k zeros are at positions zero_positions[i+1] to zero_positions[i+k]
                first_zero = zero_positions[i + 1]
                last_zero = zero_positions[i + k]
                
                # Count ones in the core window (between first and last zero)
                ones_in_core = last_zero - first_zero + 1 - k
                
                # Count extendable ones on left and right
                left_ones = first_zero - left_boundary - 1
                right_ones = right_boundary - last_zero - 1
                
                # For each valid substring containing all k zeros
                # We can extend left by 0 to left_ones, right by 0 to right_ones
                for left_extend in range(left_ones + 1):
                    for right_extend in range(right_ones + 1):
                        total_ones = ones_in_core + left_extend + right_extend
                        if total_ones >= k * k:
                            total_count += 1
    
    return total_count

• Quadratic constraint exploitation: When a problem involves a constraint like `ones ≥ zeros²`, recognize that the quadratic growth severely limits one variable - here zeros can be at most O(√n), making enumeration by the constrained variable a viable strategy even though it seems like brute force.
• Fixed-parameter enumeration pattern: Instead of iterating through all O(n²) substrings, fix the number of zeros (only ~200 possible values for n=40,000) and use two-pointers or prefix sums to count valid substrings with exactly that many zeros - this reduces complexity from O(n²) to O(n√n).
• Prefix sum with constraint checking: Maintain a prefix sum array for ones and iterate through all pairs of zero positions; for each zero-count k, check if the substring between positions has at least k² ones using O(1) prefix sum lookups, enabling efficient validation without recounting.
• Off-by-one in constraint boundaries: A critical mistake is miscounting edge cases where zeros=0 (all-ones substrings) or using `ones > zeros²` instead of `ones ≥ zeros²` - always verify your inequality direction and test boundary cases like single-character substrings and zero-free ranges separately.
• Asymmetric complexity analysis: Don't assume all O(n²) problems are intractable - when constraints create asymmetric relationships between variables, look for the bottleneck variable to enumerate; this pattern appears in problems with square roots, logarithms, or other non-linear constraints that limit search space.
• Sliding window with non-contiguous anchors: Unlike typical sliding windows that move continuously, this problem uses zero positions as anchors - iterate through combinations of zero positions to define substring boundaries, then validate the interior; this hybrid approach combines enumeration with window-based counting for problems where traditional sliding window doesn't apply directly.