Count Substrings with More 1's than 0's

Problem

Given a binary string s, count all substrings that contain more 1s than 0s.

Example

Input:

s = "011"

Output:

Explanation

The valid substrings are:

"011"
"1"
"11"
"1"

Brute Force Approach

Generate every possible substring and count the number of 0s and 1s.

for every starting index
    for every ending index
        count 0 and 1
        if (ones > zeros)
            answer++

Complexity

Time: O(N³) (or O(N²) with prefix counts)
Space: O(1)

This approach is too slow for N = 60000.

Optimized Idea

Instead of counting zeros and ones separately for every substring, convert the problem into a prefix sum problem.

Step 1: Convert Characters

Replace:

1 → +1
0 → -1

Example

becomes

-1 +1 +1 -1

Step 2: Prefix Sum

Create prefix sums.

Prefix[0] = 0

Prefix[i] = sum of first i characters

Example

String : 0 1 1

Value  : -1 +1 +1

Prefix array:

Index : 0   1   2   3
Value : 0  -1   0   1

Step 3: Substring Sum

For a substring:

l...r

its sum is:

Prefix[r + 1] - Prefix[l]

If:

sum > 0

then:

ones > zeros

Therefore:

Prefix[r + 1] > Prefix[l]

So, for every current prefix sum, we only need to know:

How many previous prefix sums are smaller than the current prefix sum?

This becomes the entire problem.

Why Fenwick Tree?

Suppose the current prefix sum is:

We need to count how many previously seen prefix sums are:

A Fenwick Tree can efficiently answer:

How many values are smaller than x?

in:

O(log N)

time.

Coordinate Compression

Prefix sums can range from:

-N to +N

For:

N = 60000

the range becomes:

-60000 ... 60000

Instead of creating a huge Fenwick Tree, compress the values.

Example

Original values:

After sorting:

Assign ranks:

The Fenwick Tree stores only these ranks.

Code Explanation

Solution Class

class Solution {

This is the main solution class.

Fenwick Tree

class Fenwick {

The Fenwick Tree supports:

Update
Prefix query

Variables

int[] bit;
int n;

bit stores frequencies.
n is the size of the tree.

Constructor

Fenwick(int n) {
    this.n = n;
    bit = new int[n + 2];
}

Creates the Fenwick Tree.

Update

void update(int idx, int val) {
    while (idx <= n) {
        bit[idx] += val;
        idx += idx & -idx;
    }
}

Adds one occurrence of a prefix sum.

Example

Current prefix sum:

update(rank(3), 1);

Now the Fenwick Tree remembers that prefix sum 3 has appeared once.

Query

int query(int idx) {
    int sum = 0;
    while (idx > 0) {
        sum += bit[idx];
        idx -= idx & -idx;
    }
    return sum;
}

Returns the number of prefix sums whose rank is less than or equal to idx.

Build Prefix Array

int[] pref = new int[n + 1];
pref[0] = 0;

The prefix sum always starts with zero.

Build Prefix Sums

for (int i = 1; i <= n; i++) {
    pref[i] = pref[i - 1] + (s.charAt(i - 1) == '1' ? 1 : -1);
}

If the current character is:

add:

+1

Otherwise, add:

-1

Example

For:

The prefix sums are:

Coordinate Compression

Copy the prefix array:

int[] arr = pref.clone();

Sort it:

Arrays.sort(arr);

Create a mapping:

HashMap<Integer, Integer> map = new HashMap<>();

Assign ranks:

int idx = 1;

for (int x : arr) {
    if (!map.containsKey(x))
        map.put(x, idx++);
}

Example

Prefix sums:

Assigned ranks:

-1 → 1
0  → 2
1  → 3

Main Logic

long ans = 0;

Stores the final answer.

Process Every Prefix Sum

for (int x : pref) {

The current prefix sum is:

Find its rank:

int pos = map.get(x);

Count all smaller prefix sums:

ans += ft.query(pos - 1);

Why?

Because:

current prefix > previous prefix

means:

substring sum > 0

which means:

ones > zeros

Insert the current prefix sum:

ft.update(pos, 1);

Now future prefix sums can use it.

Finally:

return (int) ans;

Dry Run

Input

Converted values:

-1 +1 +1

Prefix sums:

Compressed ranks:

-1 → 1
0  → 2
1  → 3

Initially, the Fenwick Tree is empty.

Prefix = 0

query(1) = 0

answer = 0

insert 0

Prefix = -1

query(0) = 0

answer = 0

insert -1

Prefix = 0

query(1) = 1

answer = 1

insert 0

Prefix = 1

query(2) = 3

answer = 4

insert 1

Final answer:

Complexity Analysis

Operation	Complexity
Prefix Sum	O(N)
Sorting	O(N log N)
Coordinate Compression	O(N)
Fenwick Tree Queries	O(N log N)

Time Complexity

O(N log N)

Space Complexity

O(N)

Java Implementation

class Solution {

    class Fenwick {

        int[] bit;
        int n;

        Fenwick(int n) {
            this.n = n;
            bit = new int[n + 2];
        }

        void update(int idx, int val) {
            while (idx <= n) {
                bit[idx] += val;
                idx += idx & -idx;
            }
        }

        int query(int idx) {
            int sum = 0;
            while (idx > 0) {
                sum += bit[idx];
                idx -= idx & -idx;
            }
            return sum;
        }
    }

    public int countSubstring(String s) {

        int n = s.length();

        int[] pref = new int[n + 1];
        pref[0] = 0;

        for (int i = 1; i <= n; i++) {
            pref[i] = pref[i - 1] + (s.charAt(i - 1) == '1' ? 1 : -1);
        }

        // Coordinate Compression
        int[] arr = pref.clone();
        java.util.Arrays.sort(arr);

        java.util.HashMap<Integer, Integer> map = new java.util.HashMap<>();

        int idx = 1;

        for (int x : arr) {
            if (!map.containsKey(x))
                map.put(x, idx++);
        }

        Fenwick ft = new Fenwick(idx);

        long ans = 0;

        for (int x : pref) {

            int pos = map.get(x);

            // Count previous prefix sums strictly smaller
            ans += ft.query(pos - 1);

            ft.update(pos, 1);
        }

        return (int) ans;
    }
}

Key Insight

The problem is transformed from counting 1s and 0s in every substring to comparing prefix sums.

Convert 1 → +1 and 0 → -1.
A substring has more 1s than 0s if its sum is positive.
A positive substring sum means the current prefix sum is greater than an earlier prefix sum.
Use a Fenwick Tree to efficiently count how many earlier prefix sums are smaller than the current one, resulting in an O(N log N) solution.

Summary

By converting the binary string into a sequence of +1 and -1 values, the problem becomes one of comparing prefix sums instead of repeatedly counting characters. Every valid substring corresponds to a pair of prefix sums where the later prefix is greater than the earlier one. Coordinate compression reduces the prefix sum range, while a Fenwick Tree efficiently counts previously seen smaller prefix sums in O(log N) time per operation. This optimization improves the overall complexity from brute force to O(N log N) with O(N) space.