Problem
Given a binary string s, count all substrings that contain more 1s than 0s.
Example
Input:
s = "011"
Output:
4
Explanation
The valid substrings are:
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
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
0110
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:
5
We need to count how many previously seen prefix sums are:
-3
-2
0
1
2
4
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:
-5
2
8
0
After sorting:
-5
0
2
8
Assign ranks:
-5 → 1
0 → 2
2 → 3
8 → 4
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:
Variables
int[] bit;
int n;
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:
3
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:
1
add:
+1
Otherwise, add:
-1
Example
For:
011
The prefix sums are:
0
-1
0
1
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:
0
-1
0
1
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:
x
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
011
Converted values:
-1 +1 +1
Prefix sums:
0
-1
0
1
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:
4
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.