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 * 104s consists only of characters '0' and '1'.This approach involves checking each substring of s. For each substring, count the number of ones and zeros, then determine if the substring has dominant ones. This method is straightforward but may be inefficient for large strings.
This C function iterates through each possible substring of the input binary string s and counts the number of ones and zeros. It then checks if the substring has dominant ones by comparing the count of ones to the square of zeros.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^3), where n is the length of the string due to nested iterations.
Space Complexity: O(1), as no additional space is utilized apart from variables.
This approach optimizes the search for all possible substrings using prefix sums. It calculates cumulative counts of ones and zeros, allowing efficient evaluation of the dominance condition by comparing only the difference between indices.
This C implementation uses arrays to store accumulated counts of ones and zeros for each position. This allows for quick determination of ones and zeros in any substring.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), with optimized substring evaluation using prefix sums.
Space Complexity: O(n), for storing prefix counts.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3), where n is the length of the string due to nested iterations. Space Complexity: O(1), as no additional space is utilized apart from variables. |
| Optimized Approach with Prefix Sum | Time Complexity: O(n^2), with optimized substring evaluation using prefix sums. Space Complexity: O(n), for storing prefix counts. |
Palindromic Substrings - Leetcode 647 - Python • NeetCode • 177,962 views views
Watch 9 more video solutions →Practice Count the Number of Substrings With Dominant Ones with our built-in code editor and test cases.
Practice on FleetCode