Today I have done leetcode's November LeetCoding Challenge with cpp.

November LeetCoding Challenge 15

Description

Count the Number of Substrings With Dominant Ones

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: 5

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'.

Solution

class Solution {
public:
  int numberOfSubstrings(string s) {
    int len = s.length();
    vector<int> zeroes;
    for(int i = 0; i < len; ++i) {
      if(s[i] == '0') zeroes.push_back(i);
    }
    int ones = len - zeroes.size();
    zeroes.push_back(len);

    int answer = 0;
    int sid = 0;
    for(int left = 0; left < len; ++left) {
      for(int id = sid; id < zeroes.size() - 1; ++id) {
        int count = id - sid + 1;
        if(count * count > ones) break;
        int p = zeroes[id];
        int q = zeroes[id + 1];
        int countNext = zeroes[id] - left - (id - sid);
        if(countNext >= count * count) {
          answer += q - p;
        } else {
          answer += max(q - p - (count * count - countNext), 0);
        }
      }
      if(s[left] == '0') {
        sid += 1;
      } else {
        answer += zeroes[sid] - left;
        ones -= 1;
      }
    }
    return answer;
  }
};

// Accepted
// 881/881 cases passed (111 ms)
// Your runtime beats 97.32 % of cpp submissions
// Your memory usage beats 66.44 % of cpp submissions (17.2 MB)

2025-11-15 Daily Challenge

November LeetCoding Challenge 15

Description

Solution