3234. Count the Number of Substrings With Dominant Ones
Approach
Sliding window; count substrings where #ones ≥ #zeros².
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.
The sliding window technique maintains a dynamic sub-array (or substring) of interest, expanding the right boundary and shrinking the left boundary based on a constraint. It reduces O(n²) substring enumeration to O(n). Track state (frequency map, sum, distinct count) incrementally.
// Approach: Sliding window; count substrings where #ones ≥ #zeros².
// Time: O(n * sqrt(n)) Space: O(1)
public class Solution
{
public int NumberOfSubstrings(string s)
{
int ans = 0;
// Iterate through all possible number of 0s.
for (int zero = 0; zero + zero * zero <= s.Length; ++zero)
{
int lastInvalidPos = -1;
int[] count = new int[2];
for (int l = 0, r = 0; r < s.Length; ++r)
{
count[s[r] - '0']++;
// Try to shrink the window to maintain the "minimum" length of the
// valid substring.
for (; l < r; ++l)
{
if (s[l] == '0' && count[0] > zero)
{
count[0]--; // Remove an extra '0'.
lastInvalidPos = l;
}
else if (s[l] == '1' && count[1] - 1 >= zero * zero)
count[1]--; // Remove an extra '1'.
else
break; // Cannot remove more characters.
}
if (count[0] == zero && count[1] >= zero * zero)
// Add valid substrings ending in s[r] to the answer. They are
// s[lastInvalidPos + 1..r], s[lastInvalidPos + 2..r], ..., s[l..r].
ans += l - lastInvalidPos;
}
}
return ans;
}
}