Count the Number of Substrings With Dominant Ones

Count the Number of Substrings With Dominant Ones - Problem

String Enumeration Medium

You are given a binary string s. Return the number of substrings with dominant ones.

A string has dominant ones if the number of ones in the string is greater than or equal to the square of the number of zeros in the string.

In mathematical terms, for a substring with ones count of 1s and zeros count of 0s: ones ≥ zeros²

Input & Output

Example 1 — Basic Case

$ Input: s = "00011"

› Output: 5

💡 Note: Valid substrings: "1" (ones=1 ≥ zeros²=0), "11" (ones=2 ≥ zeros²=0), "1" (ones=1 ≥ zeros²=0), "01" (ones=1 ≥ zeros²=1), "011" (ones=2 ≥ zeros²=1)

Example 2 — All Ones

$ Input: s = "101101"

› Output: 15

💡 Note: Most substrings work since zeros are limited: single 1s, pairs like "10", "01", and longer valid combinations

Example 3 — Many Zeros

$ Input: s = "1000"

› Output: 1

💡 Note: Only "1" at the start works. Other substrings have too many zeros: "10" needs 1≥1 (ok), "100" needs 1≥4 (fail), "1000" needs 1≥9 (fail)

Constraints

1 ≤ s.length ≤ 4 × 10⁴
s consists only of characters '0' and '1'

Visualization

Tap to expand

Understanding the Visualization

Input String

Binary string s with 0s and 1s

Check Condition

For each substring: count ones ≥ (count zeros)²

Count Valid

Return total number of valid substrings

Key Takeaway

🎯 Key Insight: Large zero counts make the constraint very restrictive - use this for early termination!

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is that when zeros become large, the condition ones ≥ zeros² becomes very restrictive, allowing for early termination optimizations. The brute force approach checks all O(n²) substrings in O(n³) time, while the optimized version uses mathematical constraints to prune impossible cases. Best approach uses early termination: Time O(n²), Space O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Substrings	O(n³)	O(1)	Generate all possible substrings and check the dominant ones condition
Optimized - Group by Zero Count	O(n²)	O(n)	Process substrings grouped by number of zeros to reduce redundant work

Brute Force - Check All Substrings — Algorithm Steps

Iterate through all starting positions i
For each i, iterate through all ending positions j ≥ i
Count ones and zeros in substring s[i:j+1]
Check if ones ≥ zeros² and increment counter

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Substrings

Create all possible substrings from each starting position

Count 1s and 0s

For each substring, count ones and zeros

Check Condition

Verify if ones ≥ zeros² and increment counter

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int solution(char* s) {
    int n = strlen(s);
    int count = 0;
    
    for (int i = 0; i < n; i++) {
        int ones = 0;
        int zeros = 0;
        for (int j = i; j < n; j++) {
            if (s[j] == '1') {
                ones++;
            } else {
                zeros++;
            }
            
            if (ones >= zeros * zeros) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char s[100005];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int result = solution(s);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops: O(n²) substrings × O(n) counting for each

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to track counts and result

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Substrings — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler