3234. Count the Number of Substrings With Dominant Ones

[mah-shamim]

Topics: String, Sliding Window, Enumeration, Weekly Contest 408

You are given a binary string s.

Return the number of substrings¹ with dominant ones.

A string has dominant ones if the number of ones in the string is greater than or equal to the square of the number of zeros in the string.

Example 1:

• Input: s = "00011"

• Output: 2

• Explanation: The substrings with dominant ones are shown in the table below.

  i	j	s[i..j]	Number of Zeros	Number of Ones
  3	3	1	0	1
  4	4	1	0	1
  2	3	01	1	1
  3	4	11	0	2
  2	4	011	1	2

Example 2:

• Input: s = "101101"

• Output: 16

• Explanation: The substrings with non-dominant ones are shown in the table below.

  • Since there are 21 substrings total and 5 of them have non-dominant ones, it follows that there are 16 substrings with dominant ones.

  i	j	s[i..j]	Number of Zeros	Number of Ones
  1	1	0	1	0
  4	4	0	1	0
  1	4	0110	2	2
  0	4	10110	2	3
  1	5	01101	2	3

Constraints:

• 1 <= s.length <= 4 * 10⁴
• s consists only of characters '0' and '1'.

Hint:

1. Let us fix the starting index l of the substring and count the number of indices r such that l <= r and the substring s[l..r] has dominant ones.
2. A substring with dominant ones has at most sqrt(n) zeros.
3. We cannot iterate over every r and check if the s[l..r] has dominant ones. Instead, we iterate over the next sqrt(n) zeros to the left of l and count the number of substrings with dominant ones where the current zero is the rightmost zero of the substring.

Footnotes

1. Substring: A substring is a contiguous non-empty sequence of characters within a string. ↩

[mah-shamim]

We need to count the number of substrings in a binary string where the number of ones is greater than or equal to the square of the number of zeros. The challenge is to efficiently compute this without checking every possible substring explicitly, which would be computationally expensive for large strings.

Approach:

1. Problem Analysis: The problem requires checking all possible substrings of the given binary string to determine if they meet the condition where the number of ones is at least the square of the number of zeros. Directly checking all substrings would result in an O(n^2) solution, which is inefficient for large strings (n up to 40,000).

2. Key Insight: For any substring to satisfy the condition, the number of zeros in the substring must be limited. Specifically, if a substring has k zeros, it must have at least k^2 ones. Given the constraints, the maximum number of zeros in any valid substring cannot exceed a certain limit (since k^2 must be ≤ the substring length). This limit is approximately the square root of the string length, which is around 200 for n=40,000.

3. Algorithm Selection: We use a sliding window approach combined with preprocessing to efficiently count valid substrings. The steps are:

   • Precompute the positions of all zeros in the string.
   • For each starting index l of the substring, determine the range of ending indices r such that the substring s[l..r] has at most 200 zeros and satisfies the condition.
   • Use the precomputed zero positions to quickly find the number of zeros in any substring and check the condition.

4. Complexity Analysis: The algorithm processes each starting index l and checks up to 200 possible zeros, leading to an O(200 * n) time complexity, which is efficient for the given constraints.

Let's implement this solution in PHP: 3234. Count the Number of Substrings With Dominant Ones

<?php
/**
 * @param String $s
 * @return Integer
 */
function numberOfSubstrings($s) {
    $n = strlen($s);
    $pre0 = array_fill(0, $n + 1, 0);
    $zeros = [];
    for ($i = 0; $i < $n; $i++) {
        $pre0[$i + 1] = $pre0[$i] + ($s[$i] == '0' ? 1 : 0);
        if ($s[$i] == '0') {
            $zeros[] = $i;
        }
    }
    $totalZeros = count($zeros);
    $count = 0;
    for ($l = 0; $l < $n; $l++) {
        $idx0 = $pre0[$l];
        if ($idx0 < $totalZeros) {
            $firstZero = $zeros[$idx0];
        } else {
            $firstZero = $n;
        }
        $count += ($firstZero - $l);

        for ($k = 1; $k <= 200; $k++) {
            if ($idx0 + $k - 1 >= $totalZeros) {
                break;
            }
            $p = $zeros[$idx0 + $k - 1];
            if ($idx0 + $k < $totalZeros) {
                $q = $zeros[$idx0 + $k];
            } else {
                $q = $n;
            }
            $rMinValid = $l + $k * $k + $k - 1;
            if ($rMinValid < $p) {
                $startR = $p;
            } else {
                $startR = $rMinValid;
            }
            if ($startR < $q) {
                $count += ($q - $startR);
            }
        }
    }
    return $count;
}

// Test cases
echo numberOfSubstrings("00011") . "\n";    // Output: 5
echo numberOfSubstrings("101101") . "\n";   // Output: 16
?>

Explanation:

1. Preprocessing: We first compute an array pre0 where pre0[i] stores the number of zeros from the start of the string up to index i-1. We also store the positions of all zeros in the array zeros.

2. Counting Valid Substrings: For each starting index l, we calculate the number of valid substrings starting at l:

   • Zero-length check: For substrings with zero zeros (all ones), all substrings starting at l until the first zero are valid. This is handled by $count += ($firstZero - $l).
   • Non-zero zeros: For substrings with k zeros (from 1 to 200), we check if the substring length is at least k^2 + k. Using the precomputed zero positions, we determine the range of r where the substring s[l..r] has exactly k zeros and meets the length condition. The count of such valid substrings is added to the total.

3. Efficiency: By limiting the check to at most 200 zeros per starting index, the algorithm efficiently computes the result in linear time relative to the string length, making it suitable for large inputs.

[basharul-siddike]

Thanks for solving the problem of "Count the Number of Substrings With Dominant Ones"

[mah-shamim]

Thanks