Count the Number of Substrings With Dominant Ones

Count the Number of Substrings With Dominant Ones

What is this problem about?

The Count the Number of Substrings With Dominant Ones interview question involves a binary string. A substring is considered to have "dominant ones" if the count of '1's in it is at least the square of the count of '0's in it ($count_1 \ge count_0^2$).

You need to find the total number of such substrings.

Why is this asked in interviews?

This "Medium" problem is used by Meta, Amazon, and Google to test optimization of the sliding window interview pattern or enumeration. The key insight is that since $count_1 \le N$, and $count_1 \ge count_0^2$, the number of zeros in a valid substring is bounded by $\sqrt{N}$. This allows you to iterate over the number of zeros rather than the substring boundaries.

Algorithmic pattern used

The problem uses Enumeration by Zeros.

1. Record the indices of all '0's in the string.
2. Iterate through each index i as the start of a substring.
3. For each i, iterate through the upcoming '0's. Since $count_0 \le \sqrt{N}$, you only check about $\sim 200$ zeros even for $N=40,000$.
4. For each number of zeros $Z$, find the range of indices $[L, R]$ that contain exactly $Z$ zeros.
5. In this range, calculate how many '1's exist and check the condition $count_1 \ge Z^2$.
6. Sum the counts.

Example explanation

s = "1011", $count_1 \ge count_0^2$

1. Start at i=0:
   • 0 zeros: "1", "1...". Max 1s is 1. $1 \ge 0^2$. (Valid).
   • 1 zero: "10", "101", "1011". $count_0=1$, so need $count_1 \ge 1^2 = 1$.
     • "10": 1 one (Valid).
     • "101": 2 ones (Valid).
     • "1011": 3 ones (Valid).
2. Start at i=1... and so on.

Common mistakes candidates make

• Brute force: $O(N^2)$ will be too slow if $N=40,000$.
• Off-by-one: Incorrectly identifying the range of indices between zeros.
• Ignoring the square: Getting the condition $count_1 \ge count_0$ mixed up with $count_1 \ge count_0^2$.

Interview preparation tip

Whenever a problem involves a constraint like $X \ge Y^2$, check the bounds of $Y$. If $X$ is bounded by $N$, then $Y$ is bounded by $\sqrt{N}$. Reducing a search space from $N$ to $\sqrt{N}$ is a common "Medium to Hard" optimization trick.