Count the Number of Substrings With Dominant Ones

1. Initialize a variable ans to 0 to store the count of dominant substrings.
2. Use a nested loop to iterate through all possible substrings. The outer loop variable i represents the start of the substring, and the inner loop variable j represents the end.
3. For each starting index i, initialize counts for zeros and ones to 0.
4. In the inner loop, for each character s[j], update the counts of zeros and ones for the substring s[i..j].
5. Check if the condition ones >= zeros * zeros is met.
6. If the condition is true, increment ans.
7. After iterating through all substrings, return ans.

We can use two nested loops to define all substrings. The outer loop iterates through all possible starting indices i from 0 to n-1, and the inner loop iterates through all possible ending indices j from i to n-1, where n is the length of the string.

For each substring s[i..j], we can maintain a running count of zeros (zeros) and ones (ones). As we extend the substring by moving j from i to n-1, we update these counts. After each update, we check if the condition ones >= zeros * zeros holds. If it does, we increment our total count of dominant substrings.

Here is the algorithm:

1. Initialize a counter ans to 0.
2. Loop for i from 0 to n-1: a. Initialize zeros = 0 and ones = 0. b. Loop for j from i to n-1: i. If s[j] is '0', increment zeros. Otherwise, increment ones. ii. Check if ones >= zeros * zeros. iii. If the condition is true, increment ans.
3. Return ans.

1class Solution {2    public long countSubstrings(String s) {3        int n = s.length();4        long ans = 0;5        for (int i = 0; i < n; i++) {6            int zeros = 0;7            int ones = 0;8            for (int j = i; j < n; j++) {9                if (s.charAt(j) == '0') {10                    zeros++;11                } else {12                    ones++;13                }14                if (ones >= (long)zeros * zeros) {15                    ans++;16                }17            }18        }19        return ans;20    }21}

1. Pre-process the string to get a list of all indices where '0' appears. Let's call it zeroIndices.
2. Initialize a total count ans to 0.
3. Iterate through the string with an index i from 0 to n-1, representing the start of a substring.
4. For each i, find the index zeroPtr in zeroIndices corresponding to the first '0' at or after i.
5. First, count substrings with zero '0's. These are substrings starting at i and ending before the '0' at zeroIndices[zeroPtr]. All such non-empty substrings are dominant. Add their count to ans.
6. Then, iterate for the number of zeros c0 from 1 up to sqrt(n). We can stop at sqrt(n) because if c0 > sqrt(n), then c0*c0 > n, making the condition c1 >= c0*c0 impossible to satisfy as c1 <= n.
7. For each c0, determine the range of ending indices j such that s[i..j] has exactly c0 zeros. This range is bounded by the c0-th and (c0+1)-th zeros from zeroPtr.
8. Calculate the minimum j required by the dominance condition: j >= i + c0*c0 + c0 - 1.
9. The number of valid substrings for this i and c0 is the size of the intersection of the two ranges for j. Add this number to ans.
10. Return ans after the outer loop finishes.

The algorithm iterates through each index i as a potential start of a substring. For each i, we calculate the number of dominant substrings starting at i.

We can handle two cases for the number of zeros (c0) in a substring s[i..j]:

1. c0 = 0: The substring contains only '1's. The condition c1 >= 0*0 is always true for non-empty substrings. We can find the next occurrence of '0' after i (or the end of the string) and add all substrings s[i..j] within this range to the count.
2. c0 > 0: We can iterate through the possible number of zeros, c0, from 1 up to sqrt(N). For a fixed i and c0, we can determine the exact range of ending indices j for which the substring s[i..j] contains exactly c0 zeros. This range is defined by the positions of the c0-th and (c0+1)-th zeros after index i. Within this range of j, we apply the dominance condition c1 >= c0*c0, which simplifies to a condition on j: j >= i + c0*c0 + c0 - 1. We can then count how many integers j fall into the intersection of these two ranges in O(1) time.

To efficiently find the positions of zeros, we can pre-process the string and store the indices of all zeros in a list.

Here is the algorithm:

1. Pre-compute a list zeroIndices containing the indices of all '0's in s.
2. Initialize ans = 0.
3. Iterate i from 0 to n-1: a. Find the index zeroPtr of the first zero in zeroIndices that is at or after i. b. Case c0 = 0: All substrings starting at i and ending before the zero at zeroIndices[zeroPtr] are dominant. Add their count to ans. c. Case c0 > 0: Loop c0 from 1 as long as c0*c0 <= n. i. Determine the range of j where s[i..j] has exactly c0 zeros. This is from the c0-th zero after i up to the character before the (c0+1)-th zero. ii. Calculate the minimum j required by the dominance condition: minJ = i + c0*c0 + c0 - 1. iii. Find the number of j's that satisfy both conditions and add this to ans.
4. Return ans.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public long countSubstrings(String s) {6        int n = s.length();7        long count = 0;8 9        List<Integer> zeroIndices = new ArrayList<>();10        for (int i = 0; i < n; i++) {11            if (s.charAt(i) == '0') {12                zeroIndices.add(i);13            }14        }15        int numZeros = zeroIndices.size();16 17        int zeroPtr = 0;18        for (int i = 0; i < n; i++) {19            // Find the first zero at or after index i20            while (zeroPtr < numZeros && zeroIndices.get(zeroPtr) < i) {21                zeroPtr++;22            }23 24            // Case 1: Substrings with c0 = 0 zeros25            int nextZeroPos = (zeroPtr < numZeros) ? zeroIndices.get(zeroPtr) : n;26            // All substrings s[i...j] where j is in [i, nextZeroPos - 1] have 0 zeros.27            // They are all dominant. There are (nextZeroPos - i) such substrings.28            count += (nextZeroPos - i);29 30            // Case 2: Substrings with c0 > 0 zeros31            for (int c0 = 1; (long)c0 * c0 <= n; c0++) {32                int currentZeroGroupIdx = zeroPtr + c0 - 1;33                if (currentZeroGroupIdx >= numZeros) {34                    break; // Not enough zeros left in the string35                }36 37                // A substring s[i..j] with c0 zeros must end at or after the c0-th zero from i38                // and before the (c0+1)-th zero.39                int startJRange = zeroIndices.get(currentZeroGroupIdx);40                int endJRange = (currentZeroGroupIdx + 1 < numZeros) ? zeroIndices.get(currentZeroGroupIdx + 1) - 1 : n - 1;41 42                // Dominance condition: c1 >= c0*c0  =>  (j-i+1) - c0 >= c0*c043                // => j >= i + c0*c0 + c0 - 144                long minJ = (long)i + (long)c0 * c0 + (long)c0 - 1;45 46                long validStartJ = Math.max(startJRange, minJ);47                long validEndJ = endJRange;48 49                if (validStartJ <= validEndJ) {50                    count += (validEndJ - validStartJ + 1);51                }52            }53        }54        return count;55    }56}