1class Solution {
2    public int numberOfSubstrings(String s) {
3        int length = s.length();
4
5        // nextZero[i] holds the index of the first '0' at or after position i.
6        // If there is no '0' from i onward, it equals length.
7        int[] nextZero = new int[length + 1];
8        nextZero[length] = length;
9        for (int i = length - 1; i >= 0; --i) {
10            nextZero[i] = nextZero[i + 1];
11            if (s.charAt(i) == '0') {
12                nextZero[i] = i;
13            }
14        }
15
16        int answer = 0;
17
18        // Fix the left boundary 'start' of the substring.
19        for (int start = 0; start < length; ++start) {
20            // zeroCount: number of '0's currently considered in the prefix.
21            int zeroCount = s.charAt(start) == '0' ? 1 : 0;
22            int current = start;
23
24            // Iterate while the required number of '1's (zeroCount^2)
25            // does not exceed the array size (an upper bound for feasibility).
26            while (current < length && 1L * zeroCount * zeroCount <= length) {
27                // oneCount: number of '1's in the window [start, nextZero[current + 1]).
28                // (nextZero[current + 1] - start) is the total length of that window,
29                // and subtracting zeroCount leaves the count of '1's.
30                int oneCount = nextZero[current + 1] - start - zeroCount;
31
32                // The substring is valid only when oneCount >= zeroCount^2.
33                if (oneCount >= zeroCount * zeroCount) {
34                    // Number of valid right endpoints in this segment:
35                    //   - (nextZero[current + 1] - current): the count of trailing
36                    //     '1's available before the next '0',
37                    //   - (oneCount - zeroCount^2 + 1): the count of right endpoints
38                    //     that still satisfy the ones-count constraint.
39                    // We take the smaller of the two so we don't overcount.
40                    answer += Math.min(nextZero[current + 1] - current,
41                                       oneCount - zeroCount * zeroCount + 1);
42                }
43
44                // Advance to the next '0' position and include it in the count.
45                current = nextZero[current + 1];
46                ++zeroCount;
47            }
48        }
49
50        return answer;
51    }
52}
53

1class Solution {
2public:
3    int numberOfSubstrings(string s) {
4        int n = s.size();
5
6        // next_zero[i] stores the index of the first '0' at or after position i.
7        // If no '0' exists from i onward, it stores n.
8        vector<int> next_zero(n + 1);
9        next_zero[n] = n;
10        for (int i = n - 1; i >= 0; --i) {
11            next_zero[i] = next_zero[i + 1];
12            if (s[i] == '0') {
13                next_zero[i] = i;
14            }
15        }
16
17        int ans = 0;
18
19        // Enumerate each starting index i of the substring.
20        for (int i = 0; i < n; ++i) {
21            // zero_count: number of '0's currently considered in the substring
22            // starting at i. Initialize based on whether s[i] is '0'.
23            int zero_count = (s[i] == '0') ? 1 : 0;
24
25            // j marks the position of the last '0' included (we iterate '0' by '0').
26            int j = i;
27
28            // We only need to consider substrings where zero_count^2 <= n,
29            // since the count of '1's can never exceed n.
30            while (j < n && 1LL * zero_count * zero_count <= n) {
31                // one_count: number of '1's between i and the next '0'
32                // (next_zero[j + 1]), excluding the zeros already counted.
33                int one_count = next_zero[j + 1] - i - zero_count;
34
35                // A valid substring requires one_count >= zero_count^2.
36                if (one_count >= zero_count * zero_count) {
37                    // We can extend the right end through the run of '1's that
38                    // follow position j. The right boundary can move up to
39                    // next_zero[j + 1] (the next '0'), but is also limited by
40                    // how many surplus '1's we have beyond zero_count^2.
41                    ans += min(next_zero[j + 1] - j,
42                               one_count - zero_count * zero_count + 1);
43                }
44
45                // Move j to the next '0' and increase the zero count by one,
46                // preparing to evaluate substrings containing one more '0'.
47                j = next_zero[j + 1];
48                ++zero_count;
49            }
50        }
51
52        return ans;
53    }
54};
55

1/**
2 * Counts the number of substrings where the count of '1's is greater than or
3 * equal to the square of the count of '0's.
4 *
5 * @param s - The binary input string.
6 * @returns The total number of qualifying substrings.
7 */
8function numberOfSubstrings(s: string): number {
9    const length = s.length;
10
11    // nextZero[i] holds the index of the next '0' at or after position i.
12    // If no '0' exists from i onward, it equals `length`.
13    const nextZero: number[] = Array(length + 1).fill(0);
14    nextZero[length] = length;
15    for (let i = length - 1; i >= 0; --i) {
16        nextZero[i] = nextZero[i + 1];
17        if (s[i] === '0') {
18            nextZero[i] = i;
19        }
20    }
21
22    let answer = 0;
23
24    // Enumerate each possible starting index of the substring.
25    for (let start = 0; start < length; ++start) {
26        // zeroCount tracks how many '0's are currently in the prefix [start..end].
27        let zeroCount = s[start] === '0' ? 1 : 0;
28        let end = start;
29
30        // We only continue while zeroCount^2 can still be satisfied by enough '1's.
31        // Once zeroCount^2 exceeds the total length, no valid substring can exist.
32        while (end < length && zeroCount * zeroCount <= length) {
33            // Number of '1's in the range up to the position just before the next '0'.
34            // nextZero[end + 1] is the index of the next '0' after `end`.
35            // Subtracting `start` gives the span length, and removing zeroCount
36            // leaves the count of '1's.
37            const oneCount = nextZero[end + 1] - start - zeroCount;
38
39            // The required threshold of '1's is zeroCount^2.
40            if (oneCount >= zeroCount * zeroCount) {
41                // For this fixed zeroCount, the substring's right boundary can extend
42                // across the block of consecutive '1's. Two limits apply:
43                //   1) nextZero[end + 1] - end: how far we can extend before hitting
44                //      the next '0' (which would increase zeroCount).
45                //   2) oneCount - zeroCount^2 + 1: how many extra '1's we can include
46                //      while still keeping ones >= zeroCount^2.
47                // The valid count is the minimum of these two constraints.
48                answer += Math.min(nextZero[end + 1] - end, oneCount - zeroCount * zeroCount + 1);
49            }
50
51            // Jump directly to the next '0' position and account for it.
52            end = nextZero[end + 1];
53            ++zeroCount;
54        }
55    }
56
57    return answer;
58}
59