3234. Count the Number of Substrings With Dominant Ones LeetCode Solution
In this guide, you will get 3234. Count the Number of Substrings With Dominant Ones LeetCode Solution with the best time and space complexity. The solution to Count the Number of Substrings With Dominant Ones problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
1 <= s.length <= 4 * 104
s consists only of characters '0' and '1'.
Complexity Analysis
Time Complexity: O(n\sqrt{n})
Space Complexity: O(1)
3234. Count the Number of Substrings With Dominant Ones LeetCode Solution in C++
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;
}
}; /* code provided by PROGIEZ */
3234. Count the Number of Substrings With Dominant Ones LeetCode Solution in Java
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;
}
} // code provided by PROGIEZ
3234. Count the Number of Substrings With Dominant Ones LeetCode Solution in Python
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 # code by PROGIEZ
