Substrings with more 1's than 0's

Problem Overview

A substring has more 1s than 0s when its (+1/−1) sum is positive.

Intuition

A substring has more 1s than 0s when its (+1/−1) sum is positive. Prefix sums turn this into: count earlier prefixes strictly smaller than the current prefix. A Fenwick tree over shifted prefix sums gives O(log n) per update/query.

Algorithm

1Map 1 → +1 and 0 → −1; maintain running prefix sum.
2Offset sums by n+1 so indices stay non-negative in the BIT.
3Before processing position i, add query(prefixSum − 1) to the answer.
4Insert current prefix sum into the BIT and continue.

Example Walkthrough

Input: s = "10101"

1. Prefix sums: 0, 1, 0, 1, 0, 1.
2. At the last 1, three earlier prefixes (0, 0, 0) are smaller → three valid substrings ending here.

Output: count of valid substrings

Common Pitfalls

• Initialize the BIT with prefix sum 0 before the loop.
• Query prefixSum − 1 for strictly more 1s than 0s, not prefixSum.
• BIT size must cover range [−n, n] after offsetting.

Substrings with more 1's than 0's.java

Java

// Approach: Map 1→+1, 0→−1. A substring has more 1s than 0s when an earlier prefix sum is
// strictly less than the current one. Count with a Fenwick tree over shifted prefix sums.
// Time: O(n log n) Space: O(n)

class Solution {

    private void update(int[] bit, int idx, int val) {
        for (; idx < bit.length; idx += idx & -idx) {
            bit[idx] += val;
        }
    }

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

    public int countSubstring(String s) {
        int n = s.length();
        int offset = n + 1;
        int[] bit = new int[2 * n + 3];

        int currentSum = 0;
        int totalSubstrings = 0;

        update(bit, offset, 1);

        for (int i = 0; i < n; i++) {
            currentSum += s.charAt(i) == '1' ? 1 : -1;
            totalSubstrings += query(bit, currentSum + offset - 1);
            update(bit, currentSum + offset, 1);
        }

        return totalSubstrings;
    }
}

Was this solution helpful?