Skip to content

3234. Count the Number of Substrings With Dominant Ones 👍

  • Time: $O(n\sqrt{n})$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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;
      vector<int> count(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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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.charAt(r) - '0'];
        // Try to shrink the window to maintain the "minimum" length of the
        // valid substring.
        for (; l < r; ++l)
          if (s.charAt(l) == '0' && count[0] > zero) {
            --count[0]; // Remove an extra '0'.
            lastInvalidPos = l;
          } else if (s.charAt(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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
  def numberOfSubstrings(self, s: str) -> int:
    ans = 0
    #    z^2 + z = n.
    # => z^2 + z - n = 0.
    # => z = (-1 + sqrt(1 + 4n)) / 2.
    maxZero = (-1 + math.sqrt(1 + 4 * len(s))) // 2

    # Iterate through all possible number of 0s.
    for zero in range(int(maxZero) + 1):
      lastInvalidPos = -1
      count = [0, 0]
      l = 0
      for r, c in enumerate(s):
        count[int(c)] += 1
        # Try to shrink the window to maintain the "minimum" length of the
        # valid substring.
        while l < r:
          if s[l] == '0' and count[0] > zero:
            count[0] -= 1  # Remove an extra '0'.
            lastInvalidPos = l
            l += 1
          elif s[l] == '1' and count[1] - 1 >= zero * zero:
            count[1] -= 1  # Remove an extra '1'.
            l += 1
          else:
            break  # Cannot remove more characters.
        if count[0] == zero and 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