Count the Number of Substrings With Dominant Ones
Problem Description
You are given a binary string s.
A string is called a good substring if it has dominant ones i.e. if the number of ones in the string is greater than or equal to the square of the number of zeros in that particular substring.
Return the number of good substrings.
Explanation
We are given a binary string i.e a string with only 0s and 1s . We are asked to find out the number of substrings where the frequency of number of 1s is greater than or equal to the square of the frequency of number of 0s in that particular substring.
Mathematically,
freq(1) >= ((freq(0)^2)
What is a Binary String ?
A string with its characters as only 0s or 1s.
What is a Substring?
A substring is a contiguous sequence of characters within a string. For a string s = "0110", a substring must consist of characters that appear consecutively in the original string.
Single-character substrings:
"0", "1"
Two-character substrings:
"01", "11", "10"
Three-character substrings:
"011", "110"
Four-character substrings:
“0110"
Invalid Substrings (Non-contiguous sequences):
"010", is not a substring because they skip over characters or mix up the order of characters in s.
Examples
Input: s = "00011"
Output: 5
Explanation:
The substrings with dominant ones are shown in the table below.
Input: s = "101101"
Output: 16
Explanation:
The substrings with non-dominant ones are shown in the table below.
Since there are 21 substrings in total, and 5 of them are non-dominant, there are 16 substrings with dominant ones.
Constraints:
- 1 <= s.length <= 4 * 10^4
- s consists only of characters '0' and '1'.
Brute Force Approach
Intuition
The first thought that came to our mind was to generate all possible substrings of the given string and then figure out which substrings have the dominant number of 1s. right ??
Possibly, yes
How to generate Substring of a String ?
To generate all substrings of s, we will be using two loops.
We will start from the first character and move through each character of the string one by one. For each character, this is considered as the starting point of the substring.
For each starting character, we iterate over the next character and will continue till the end of the string. We will consider every possible ending point for the substring, ensuring that the ending index is always greater than the starting point (so you get non-empty substrings).
For each pair of start and end points, a substring is formed by selecting characters between the start index and one less than the end index. This way, we will be building all possible substrings.
For example if s = “00011”,
The start point = 0
The end point = 1
The highlighted part is the substring formed in “00011”.
Then the end point increments to the next index i.e end point = 2
The highlighted part is the substring formed in “00011”.
Similarly, we will move the end point till the end of the substring.
Once the end point reaches the end of the substring. We will increment the start point and start the same procedure all again until our start point is equal to the length of the substring.
When the start point =1
The end point = 2
The highlighted part is the substring formed , “00011”
The next substring formed is the highlighted part in “00011”.
Once, we generate all possible substring of the given string.
We can check the number of 1s and 0s present in the substring and then we can evaluate if the number of 1s is greater than or equal to square of no of 0s in that particular substring.
Approach:
- Outer Loop: Iterates over each possible starting index i in the string.
- Inner Loop: Iterates over each possible ending index j for a given starting index i, effectively generating all substrings.
- Counting: For each substring generated, count the number of '1's and '0's.
- Condition Check: If the number of '1's is greater than or equal to the square of the number of '0's, increment the count.
Dry-Run
String s= “101011”
Answer= 14
Explanation:- There are 14 substrings where the frequency of 1s is greater than or equal to the frequency of 0s.
Substrings starting at index 0:
"1" → 1s = 1, 0s = 0 → 1≥0^2 → Count it
"10" → 1s = 1, 0s = 1 → 1≥1^2 → Count it
"101" → 1s = 2, 0s = 1 → 2≥1^2 → Count it
"1010" → 1s = 2, 0s = 2 → 2≥2^2 → Skip it
"10101" → 1s = 3, 0s = 2 → 3≥2^2 → Skip it
"101011" → 1s = 4, 0s = 2 → 4≥2^2 → Count it
Substrings starting at index 1:
"0" → 1s = 0, 0s = 1 → 0≥1^2 → Skip it
"01" → 1s = 1, 0s = 1 → 1≥1^2 → Count it
"010" → 1s = 1, 0s = 2 → 1≥2^2 → Skip it
"0101" → 1s = 2, 0s = 2 → 2≥2^2 → Skip it
"01011" → 1s = 3, 0s = 2 → 3≥2^2 → Skip it
Substrings starting at index 2:
"1" → 1s = 1, 0s = 0 → 1≥0^2 → Count it
"10" → 1s = 1, 0s = 1 → 1≥1^2 → Count it
"101" → 1s = 2, 0s = 1 → 2≥1^2 → Count it
"1011" → 1s = 3, 0s = 1 → 3≥1^2 → Count it
Substrings starting at index 3:
"0" → 1s = 0, 0s = 1 → 0≥1^2 → Skip it
"01" → 1s = 1, 0s = 1 → 1≥1^2 → Count it
"011" → 1s = 2, 0s = 1 → 2≥1^2 → Count it
Substrings starting at index 4:
"1" → 1s = 1, 0s = 0 → 1≥0^2 → Count it
"11" → 1s = 2, 0s = 0 → 2≥0^2 → Count it
Substrings starting at index 5:
"1" → 1s = 1, 0s = 0 → 1≥0^2 → Count it
Total Valid Substrings
If we tally all the valid substrings, we get exactly 14, which matches the expected answer.
The code appears to function correctly for s = "101011", producing the expected output of 14.
Brute Force Code for all languages
1. C++ Try on Compiler
class Solution {
public:
int numberOfSubstrings(string s) {
int n = s.length();
int count = 0;
// Outer loop to set the start index of substrings
for (int i = 0; i < n; i++) {
int zeros = 0, ones = 0;
// Inner loop to set the end index and generate substrings of all sizes starting from i
for (int j = i; j < n; j++) {
// Count zeros and ones as we expand the substring
if (s[j] == '0') {
zeros++;
} else if (s[j] == '1') {
ones++;
}
// Check if the number of ones is greater than or equal to square of zeros
if (ones >= zeros * zeros) {
count++;
}
}
}
return count;
}
};2. Java Try on Compiler
class Solution {
public int numberOfSubstrings(String s) {
int n = s.length();
int count = 0;
// Outer loop to set the start index of substrings
for (int i = 0; i < n; i++) {
int zeros = 0, ones = 0;
// Inner loop to set the end index and generate substrings of all sizes starting from i
for (int j = i; j < n; j++) {
// Count zeros and ones as we expand the substring
if (s.charAt(j) == '0') {
zeros++;
} else if (s.charAt(j) == '1') {
ones++;
}
// Check if the number of ones is greater than or equal to square of zeros
if (ones >= zeros * zeros) {
count++;
}
}
}
return count;
}
}3. Python Try on Compiler
class Solution(object):
def numberOfSubstrings(self, s):
n = len(s)
count = 0
# Outer loop to set the start index of substrings
for i in range(n):
zeros, ones = 0, 0
# Inner loop to set the end index and generate substrings of all sizes starting from i
for j in range(i, n):
# Count zeros and ones as we expand the substring
if s[j] == '0':
zeros += 1
elif s[j] == '1':
ones += 1
# Check if the number of ones is greater than or equal to square of zeros
if ones >= zeros * zeros:
count += 1
return count
4. JavaScript Try on Compiler
/**
* @param {string} s
* @return {number}
*/
var numberOfSubstrings = function(s) {
const n = s.length;
let count = 0;
// Outer loop to set the start index of substrings
for (let i = 0; i < n; i++) {
let zeros = 0, ones = 0;
// Inner loop to set the end index and generate substrings
for (let j = i; j < n; j++) {
// Count zeros and ones as we expand the substring
if (s[j] === '0') {
zeros++;
} else if (s[j] === '1') {
ones++;
}
// Check if the number of ones is greater than or equal to square of zeros
if (ones >= zeros * zeros) {
count++;
}
}
}
return count;
};Time Complexity: O(n^2)
The brute-force solution involves generating all possible substrings and counting the zeros and ones in each substring.
Here's the breakdown:
The two nested loops (with indices i and j) iterate over all possible starting and ending positions of substrings.
For each starting position i, j can go from i to n-1, resulting in O(n^2) substrings overall.
The overall Time Complexity is : O(n^2).
Space Complexity: O(n)
Auxiliary Space Complexity
Auxiliary space refers to the extra space used by the algorithm aside from the input. The code only uses a few integer variables (zeros, ones, count, i, and j), all of which require O(1) space.
Each substring is temporarily created using s.substring(i, j + 1), which may use space up to O(n) for each call. However, since these substrings are not stored, the temporary space is released after each inner loop iteration.
Overall, Auxiliary Space Complexity: O(1)
Total Space Complexity
The space complexity considers the total memory used by the program, including the input and output data.
The input string s has a length of n
N, which requires O(n) space.
The output variable count uses O(1) space.
Thus, the overall total space complexity is O(n), primarily due to the storage of the input string.
The brute force method will make the interviewer unhappy. Since, the constraints of the given problem statement is 4*10^4 . The Brute force results in TLE as it will perform n^2 operations and most of the competitive environment restricts this. Let's figure out a better solution !!
Optimal Approach
Intuition
Aren't we focusing on the number of 1s to be greater than square of number of 0s ?
At each point can we know , the number of 1s we encountered and ultimately come to know the number of 0s present. For example, s= “10011”
At i= 3,
The number of 1s encountered is 2,
At i=4,
The number of 1s encountered is 3.
Is there a way to store the number of 1s encountered at each step?
We can use an array where at each index we can store the number of 1s encountered till that particular index.
We name that array a prefix array.
How a Prefix Array is created ?
Example:- s= 10101001
We will traverse each character of the string.
Start with the first number:
Look at s[0], which is 1.
Since we’re just starting, the prefix array at the first spot is just 1 (because we’ve only seen one 1 so far).
So, prefix[0] = 1.
Move to the next number and add it up:
Now, look at s[1], which is 0.
We add this to what we have seen so far. Since 0 doesn’t add anything, we still have only 1 from the beginning.
So, prefix[1] = 1.
Continue adding each number one by one:
For s[2], it’s 1 again.
Now we add this 1 to our previous total.
So, prefix[2] = 2 (because we have two 1s so far).
Keep going until the end of the string.
At the end , our prefix array will be [1, 1, 2, 2, 3, 3, 3, 4].
We will be defining the size of the prefix array to be n+1 because with a prefix array of size n + 1, the cumulative frequency at index i corresponds to the sum of frequencies from index 0 to i - 1 of the original string.
How to determine the number of 1s present between two indices ?
Its, prefix[right + 1] - prefix[left] , Why ?
Suppose arr = [0, 1, 1, 0, 1].
- Compute prefix: [0, 0, 1, 2, 2, 3]
- To count the number of 1s between left = 1 and right = 3:
Result = prefix[3 + 1] — prefix[l] = prefix[4] — prefix[l] = 2 — 0 = 2
This gives us the correct count of 1s (arr[1] + arr[2] + arr[3] = 1 + 1 + 0 = 2).
Why add 1 to right in prefix[right + 1]?
- The prefix sum at index k sums up to the element at index k - 1 in the original array.
- To include the element at right in the range, you use prefix[right + 1].
Can we determine the number of 0s present in a substring, if we know the number of 1s present in that particular substring?
Yes, number of zeros = (length of the substring - the number of 1s in that substring).
Once, we get to know the number of 0s and 1s present in the substring , we can easily declare a substring as a dominant substring if the number of 1s is greater or equal to the square of the number of 0s else not.
If it is a dominant substring, we increase our counter by 1.
But , don’t you think of some conditions , where we can just skip some of the substrings because we are too sure that the substring can be either dominant or not.
Why skipping makes sense ?
To understand why skipping helps and how we determine the amount to skip, let's go through an example step-by-step. By skipping, we avoid redundant checks for substrings that we know will either be valid (dominant) or invalid (non-dominant), saving computation time.
Example
Consider s = "10111". The task is to count substrings with dominant ones (where the number of 1s is greater than or equal to the square of the number of 0s).
Step 1: Build the Prefix Array
First, we construct a prefix array that counts the cumulative number of 1s up to each index.
For s = "10111", the prefix array one would be:
one[0] = 0 (no 1s yet)
one[1] = 1 (1 1)
one[2] = 1 (1 1)
one[3] = 2 (2 1s)
one[4] = 3 (3 1s)
one[5] = 4 (4 1s)
So, one = [0, 1, 1, 2, 3, 4].
Step 2: Evaluate Substrings with left and right Pointers
Now, we’ll use two pointers, left and right, to check each substring s[left:right] for the "dominant ones" condition:
c1≥c0^2 where:
c1 is the number of 1s in the substring.
c0 is the number of 0s in the substring.
If we observe the problem statement, it asks us to find out the number of substrings where the frequency of 1s is greater than or equal to the square of the frequency of 0s.
From the above dry run can we figure out some interesting insights ??
Did we just observe that if the length of a good string or a dominant substring is 9 .Either we can have:-
- nine 1s and zero 0s (9 >= 0^2)
- Eight 1s and one 0s (8 >= 1^2)
- Seven 1s and two 0s (7 >= 2^2 i.e 7 >= 4)
But, can a substring of length 9 with six 1s and four 0s be called a dominant substring or a good substring?
No, because 6 is not greater than or equal to 3^2 = 9
Can we make it simple that, a substring of size n can only afford less than or equal to square root of n number of 0s, in it ??
Let’s check
A substring of length n=15 to be a dominant substring should have at most √15 no of 0s i.e 3.87 which is cumulatively equal to 3 no of 0s.I.e. either the substring can have:-
- 1 no of 0s and 14 no of 1s
- 2 no of 0s and 13 no of 1s
- 3 no of 0s and 12 no of 1s
We cannot afford 4 no of 0s and 11 no of 1s to make the substring to be called as a dominant substring.
Are we focusing on the number of 0s to be less than √n ( n is the length of the substring ) to declare a substring to be good or a dominant substring.
We can take the above insight to optimize the solution.
Still having confusion ?
Suppose left = 0 and we start with right moving from left to n-1. For each right value, if we find that a substring meets the condition, we know that extending right a bit further will likely continue to satisfy the condition (since adding more 1s makes it even more likely to be dominant). Therefore, we can "skip" some steps, moving right forward by a certain amount instead of checking every single position.
Let's work through this with the specific example:
left = 0, right = 0 (substring: "1"):
c1 = 1, c0 = 0
Condition:
1≥0^2 → true
Increment ans to count this substring.
Now, we calculate how many more positions right can skip ahead.
Skipping Steps When Condition Holds:
We can extend right to include more 1s while still maintaining the dominant condition. We calculate the maximum safe skip distance by considering the difference in c1 and c0.
In this case, a safe skip distance of 1 can be applied here, so right is incremented further by that skip amount to avoid redundant checks.
Continuing with Skip Optimization:
By calculating a safe number of positions to skip when a substring meets the condition, we can directly jump right over several positions where the substring would still satisfy the condition.
If a substring fails the condition, we can skip right to jump over several positions where it’s certain the substring won’t satisfy the condition.
By using skipping, we reduce redundant checks for both valid and invalid substrings, significantly optimizing performance for larger strings.
If, we skip these steps we are saving computation time and optimizing our algorithm.
If the substring is not dominant, we will skip to the part where we can find a dominant substring.
Approach
Convert s to an Array and Track Ones:
- Convert the string s to a character array c for easy access to each character.
Initialize a prefix sum array one to keep track of cumulative counts of 1s as we go through the string.
Prefix Array to Count 1s:
- Loop through the array c to count 1s at each position. Store this count in one[i + 1], so one[i] represents the number of 1s from the start up to index i.
This lets us easily calculate the count of 1s in any substring using the difference one[right + 1] - one[left].
Iterate through Substrings Efficiently:
- Use two nested loops with pointers left and right to consider every possible substring s[left:right] from the string.
For each substring:- Calculate c1, the number of 1s in the substring.
- Calculate c0, the number of 0s in the substring, using c0 = (right - left + 1) - c1.
Check the Dominant Condition:
- Check if the substring has dominant ones by verifying if c1 (number of 1s) is greater than or equal to c0 * c0 (square of the count of 0s).
If true, this substring is a valid answer:- Increase ans by 1.
- To optimize, compute the maximum number of consecutive substrings we can skip, such that all will still satisfy the condition, and jump right by that amount.
If false, jump right forward by a calculated value to skip non-dominant substrings.
Return Result:
Finally, return the count of dominant substrings stored in ans.
Dry Run
String s= “101011”
Answer= 14
Explanation:- There are 14 substrings where the frequency of 1s is greater than or equal to the frequency of 0s.
Step 1: Build the Prefix Array for Counting 1s
We first create a prefix array one, which stores the cumulative count of 1s up to each index.
For s = "101011":
s = 1, 0, 1, 0, 1, 1
(prefix array) one array = 0, 1, 1, 2, 2, 3, 4
Iterations
1. left = 0
right = 0: Substring "1"
Calculate c1 = one[1] - one[0] = 1, c0 = (right - left + 1) - c1 = 1 - 1 = 0
Check if c0 * c0 <= c1 → 0 <= 1 (true)
Count: ans = 1
right = 1: Substring "10"
c1 = one[2] - one[0] = 1, c0 = 2 - 1 = 1
Check if c0 * c0 <= c1 → 1 <= 1 (true)
Count: ans = 2
right = 2: Substring "101"
c1 = one[3] - one[0] = 2, c0 = 3 - 2 = 1
Check if c0 * c0 <= c1 → 1 <= 2 (true)
Count: ans = 3
right = 3: Substring "1010"
c1 = one[4] - one[0] = 2, c0 = 4 - 2 = 2
Check if c0 * c0 <= c1 → 4 <= 2 (false)
Skip: right += (c0 * c0 - c1 - 1) = 1, making right = 4
right = 4: Substring "10101"
c1 = one[5] - one[0] = 3, c0 = 5 - 3 = 2
Check if c0 * c0 <= c1 → 4 <= 3 (false)
Skip: right += (c0 * c0 - c1 - 1) = 0, so right remains 4
right = 5: Substring "101011"
c1 = one[6] - one[0] = 4, c0 = 6 - 4 = 2
Check if c0 * c0 <= c1 → 4 <= 4 (true)
Count: ans = 4
2. left = 1
right = 1: Substring "0"
c1 = one[2] - one[1] = 0, c0 = 1
Check if c0 * c0 <= c1 → 1 <= 0 (false)
Skip: right += (c0 * c0 - c1 - 1) = 0, so right remains 1
right = 2: Substring "01"
c1 = one[3] - one[1] = 1, c0 = 1
Check if c0 * c0 <= c1 → 1 <= 1 (true)
Count: ans = 5
right = 3: Substring "010"
c1 = one[4] - one[1] = 1, c0 = 2
Check if c0 * c0 <= c1 → 4 <= 1 (false)
Skip: right += (c0 * c0 - c1 - 1) = 2, making right = 5
right = 5: Substring "01011"
c1 = one[6] - one[1] = 3, c0 = 2
Check if c0 * c0 <= c1 → 4 <= 3 (false)
Skip: right += (c0 * c0 - c1 - 1) = 0, so right remains 5
3. left = 2
right = 2: Substring "1"
c1 = one[3] - one[2] = 1, c0 = 0
Check if c0 * c0 <= c1 → 0 <= 1 (true)
Count: ans = 6
right = 3: Substring "10"
c1 = one[4] - one[2] = 1, c0 = 1
Check if c0 * c0 <= c1 → 1 <= 1 (true)
Count: ans = 7
right = 4: Substring "101"
c1 = one[5] - one[2] = 2, c0 = 1
Check if c0 * c0 <= c1 → 1 <= 2 (true)
Count: ans = 8
right = 5: Substring "1011"
c1 = one[6] - one[2] = 3, c0 = 1
Check if c0 * c0 <= c1 → 1 <= 3 (true)
Count: ans = 9
4. left = 3
right = 3: Substring "0"
c1 = one[4] - one[3] = 0, c0 = 1
Check if c0 * c0 <= c1 → 1 <= 0 (false)
Skip: right += (c0 * c0 - c1 - 1) = 0
right = 4: Substring "01"
c1 = one[5] - one[3] = 1, c0 = 1
Check if c0 * c0 <= c1 → 1 <= 1 (true)
Count: ans = 10
right = 5: Substring "011"
c1 = one[6] - one[3] = 2, c0 = 1
Check if c0 * c0 <= c1 → 1 <= 2 (true)
Count: ans = 11
5. left = 4
right = 4: Substring "1"
c1 = one[5] - one[4] = 1, c0 = 0
Check if c0 * c0 <= c1 → 0 <= 1 (true)
Count: ans = 12
right = 5: Substring "11"
c1 = one[6] - one[4] = 2, c0 = 0
Check if c0 * c0 <= c1 → 0 <= 2 (true)
Count: ans = 13
6. left = 5
right = 5: Substring "1"
c1 = one[6] - one[5] = 1, c0 = 0
Check if c0 * c0 <= c1 → 0 <= 1 (true)
Count: ans = 14
Final Output
The final count of dominant substrings is 14.
Optimal Code for all languages
1. C++ Try on Compiler
class Solution {
public:
int numberOfSubstrings(string s) {
int n = s.length();
// Array to store the cumulative count of '1's at each position
std::vector<int> one(n + 1, 0);
// Counter to keep track of the total number of '1's encountered
int count = 0;
// Loop through each character in the string
for (int i = 0; i < n; i++) {
// If the character is '1', increment the count
if (s[i] == '1')
count++;
// Store the cumulative count of '1's up to the current position
one[i + 1] = count;
}
// Initialize the answer to store the total count of valid substrings
int ans = 0;
// Loop over each starting point of substrings
for (int left = 0; left < n; left++) {
// Loop over each endpoint for substrings starting at 'left'
for (int right = left; right < n; right++) {
// Calculate the number of '1's in the current substring
int c1 = one[right + 1] - one[left];
// Calculate the number of '0's in the current substring
int c0 = right - left + 1 - c1;
// Check if the condition for the valid substring is met
if (c0 * c0 <= c1) {
// If valid, increment the answer count
ans++;
// Calculate an optimization value for skipping unnecessary checks
int val = std::min(std::max((int)std::sqrt(c1) - c0 - 1, 0), n - 1 - right);
// Skip unnecessary checks by moving 'right' forward
right += val;
// Add skipped values to the answer count
ans += val;
} else {
// If not valid, adjust 'right' to skip based on 'c0' and 'c1'
right += c0 * c0 - c1 - 1;
}
}
}
// Return the total count of valid substrings
return ans;
}
};2. Java Try on Compiler
class Solution {
public int numberOfSubstrings(String s) {
// Convert the input string to a character array for easy access
char[] c = s.toCharArray();
// Store the length of the string
int n = s.length();
// Array to store the cumulative count of '1's at each position
int[] one = new int[n + 1];
// Counter to keep track of the total number of '1's encountered
int count = 0;
// Loop through each character in the string
for (int i = 0; i < n; i++) {
// If the character is '1', increment the count
if (c[i] == '1')
count++;
// Store the cumulative count of '1's up to the current position
one[i + 1] = count;
}
// Initialize the answer to store the total count of valid substrings
int ans = 0;
// Loop over each starting point of substrings
for (int left = 0; left < n; left++) {
// Loop over each endpoint for substrings starting at 'left'
for (int right = left; right < n; right++) {
// Calculate the number of '1's in the current substring
int c1 = one[right + 1] - one[left];
// Calculate the number of '0's in the current substring
int c0 = right - left + 1 - c1;
// Check if the condition for the valid substring is met
if (c0 * c0 <= c1) {
// If valid, increment the answer count
ans++;
// Calculate an optimization value for skipping unnecessary checks
int val = Math.min(Math.max((int) Math.sqrt(c1) - c0 - 1, 0), n - 1 - right);
// Skip unnecessary checks by moving 'right' forward
right += val;
// Add skipped values to the answer count
ans += val;
} else {
// If not valid, adjust 'right' to skip based on 'c0' and 'c1'
right += c0 * c0 - c1 - 1;
}
}
}
// Return the total count of valid substrings
return ans;
}
}3. Python Try on Compiler
class Solution(object):
def numberOfSubstrings(self, s):
# Convert the input string to a list of characters
n = len(s)
# Array to store the cumulative count of '1's at each position
one = [0] * (n + 1)
# Counter to keep track of the total number of '1's encountered
count = 0
# Loop through each character in the string
for i in range(n):
# If the character is '1', increment the count
if s[i] == '1':
count += 1
# Store the cumulative count of '1's up to the current position
one[i + 1] = count
# Initialize the answer to store the total count of valid substrings
ans = 0
# Loop over each starting point of substrings
for left in range(n):
# Loop over each endpoint for substrings starting at 'left'
right = left
while right < n:
# Calculate the number of '1's in the current substring
c1 = one[right + 1] - one[left]
# Calculate the number of '0's in the current substring
c0 = (right - left + 1) - c1
# Check if the condition for the valid substring is met
if c0 * c0 <= c1:
# If valid, increment the answer count
ans += 1
# Calculate an optimization value for skipping unnecessary checks
val = min(max(int(math.sqrt(c1)) - c0 - 1, 0), n - 1 - right)
# Skip unnecessary checks by moving 'right' forward
right += val
# Add skipped values to the answer count
ans += val
else:
# If not valid, adjust 'right' to skip based on 'c0' and 'c1'
right += c0 * c0 - c1 - 1
# Increment 'right' for the next loop iteration
right += 1
# Return the total count of valid substrings
return ans
4. JavaScript Try on Compiler
/**
* @param {string} s
* @return {number}
*/
var numberOfSubstrings = function(s) {
const n = s.length;
// Array to store the cumulative count of '1's at each position
const one = Array(n + 1).fill(0);
// Counter to keep track of the total number of '1's encountered
let count = 0;
// Populate the cumulative count of '1's
for (let i = 0; i < n; i++) {
if (s[i] === '1') count++;
one[i + 1] = count;
}
// Initialize the result
let ans = 0;
// Iterate over all possible substrings
for (let left = 0; left < n; left++) {
for (let right = left; right < n; right++) {
const c1 = one[right + 1] - one[left]; // Count of '1's
const c0 = right - left + 1 - c1; // Count of '0's
if (c0 * c0 <= c1) {
ans++;
// Optimization: Skip unnecessary checks
const val = Math.min(
Math.max(Math.floor(Math.sqrt(c1)) - c0 - 1, 0),
n - 1 - right
);
right += val;
ans += val;
} else {
right += c0 * c0 - c1 - 1;
}
}
}
return ans;
};Time Complexity: O(n^2)
Preprocessing Step:
- The initial for loop goes through the input string s of length n to build the cumulative count array one. This loop runs in O(n) time.
Main Nested Loop:
- The function then has a nested loop where left iterates from 0 to n−1 and right iterates from left to n−1.
- In the worst case, the inner loop might run approximately n−left times for each position of left.
- This nested structure suggests an upper bound of O(n^2) for the worst case.
Space Complexity: O(n)
Auxiliary Space Complexity
- The one array of length n+1 is used to store cumulative counts of '1's. This requires O(n) additional space.
- Apart from this array, a few variables (count, ans, c1, c0, val) are used, which consume O(1) space.
Thus, the auxiliary space complexity is O(n) due to the one array.
Total Space Complexity
The total space complexity includes both the input and the auxiliary space:
- Input Space: The input string s requires O(n) space.
- Auxiliary Space: As analyzed above, it requires O(n) space for the cumulative count array.
Therefore, the total space complexity is also O(n).
Learning Tip:
Given a binary string s, return the number of non-empty substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively.
Substrings that occur multiple times are counted the number of times they occur.
Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".
The testcases will be generated such that the answer is unique.