30% off Lifetime Premium Access expires December 2nd!

30% off Lifetime Premium Access expires Dec 2nd!

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Get Premium

Leetcode 3234. Count the Number of Substrings With Dominant Ones

Given a binary string s (length ≤ 4×10^4), count substrings where the number of '1's is at least the square of the number of '0's. Key observation: zeros^2 grows fast, so any qualifying substring has O(√n) zeros, enabling enumeration by zero-count combined with prefix sums or two‑pointer counting for an efficient solution.

DESCRIPTION

Input:


s = "00011"

Output:

Explanation: Qualifying substrings: "0" (1 one, 0 zeros: 1>=0), "0" (another single zero), "1" (three times), "11" (2 ones, 0 zeros: 2>=0), "011" (2 ones, 1 zero: 2>=1). Total: 2 + 3 + 1 + 2 = 8

Constraints:

1 <= s.length <= 4×10^4
s consists only of characters '0' and '1'
A substring is a contiguous sequence of characters
The condition is: count('1') >= count('0')^2

Understanding the Problem

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).

Brute Force Approach

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

Start brute force: check all substrings

0 / 102

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n^3) Two nested loops generate O(n^2) substrings, and counting ones/zeros for each substring takes O(n) time in the worst case, resulting in O(n^3) total time

Space Complexity: O(1) Only a constant amount of extra space is needed for counters and loop variables

Building Intuition

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!

Common Mistakes

Attempting to check all O(n^2) substrings without recognizing the √n constraint on zeros, leading to O(n^3) or O(n^2) solutions that are too slow

Incorrectly implementing the sliding window for a fixed zero-count - forgetting to handle edge cases where the window reaches the string boundaries

Off-by-one errors when counting substrings within a window - need to carefully count all valid starting and ending positions

Not handling the k=0 case (substrings with no zeros) separately, which requires counting all contiguous sequences of ones

Integer overflow when computing zeros^2 for large zero counts, though this is less likely given the √n bound

Optimal Solution

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

start

Start counting substrings with dominant ones

0 / 95

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n√n) We enumerate O(√n) possible zero-counts, and for each zero-count, we scan the string once in O(n) time using a sliding window, resulting in O(n√n) total time

Space Complexity: O(1) Only a constant amount of extra space is needed for window pointers, counters, and the running total

What We've Learned

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.

Test Your Understanding

Why is sliding-window the right data structure for this problem?

sliding-window provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 3234. Count the Number of Substrings With Dominant Ones

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact