Scale Engineer

Count the Number of Substrings With Dominant Ones

Med
#2872Time: O(N^2), where N is the length of the string `s`. The two nested loops iterate through all possible substrings, which are O(N^2) in number. For each substring, the check is an O(1) operation.Space: O(1), as we only use a few variables to store the counts and the final answer, regardless of the input string size.
Patterns
Sliding WindowEnumeration
Data structures
String

Prompt

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 * 104
  • s consists only of characters '0' and '1'.

Approaches

2 approaches with complexity analysis and trade-offs.

The most straightforward approach is to generate every possible substring of the input string s, and for each substring, check if it satisfies the 'dominant ones' condition. A substring is dominant if the count of '1's is greater than or equal to the square of the count of '0's.

Algorithm

  1. Initialize a variable ans to 0 to store the count of dominant substrings.
  2. Use a nested loop to iterate through all possible substrings. The outer loop variable i represents the start of the substring, and the inner loop variable j represents the end.
  3. For each starting index i, initialize counts for zeros and ones to 0.
  4. In the inner loop, for each character s[j], update the counts of zeros and ones for the substring s[i..j].
  5. Check if the condition ones >= zeros * zeros is met.
  6. If the condition is true, increment ans.
  7. After iterating through all substrings, return ans.

Walkthrough

We can use two nested loops to define all substrings. The outer loop iterates through all possible starting indices i from 0 to n-1, and the inner loop iterates through all possible ending indices j from i to n-1, where n is the length of the string.

For each substring s[i..j], we can maintain a running count of zeros (zeros) and ones (ones). As we extend the substring by moving j from i to n-1, we update these counts. After each update, we check if the condition ones >= zeros * zeros holds. If it does, we increment our total count of dominant substrings.

Here is the algorithm:

  1. Initialize a counter ans to 0.
  2. Loop for i from 0 to n-1: a. Initialize zeros = 0 and ones = 0. b. Loop for j from i to n-1: i. If s[j] is '0', increment zeros. Otherwise, increment ones. ii. Check if ones >= zeros * zeros. iii. If the condition is true, increment ans.
  3. Return ans.
class Solution {    public long countSubstrings(String s) {        int n = s.length();        long ans = 0;        for (int i = 0; i < n; i++) {            int zeros = 0;            int ones = 0;            for (int j = i; j < n; j++) {                if (s.charAt(j) == '0') {                    zeros++;                } else {                    ones++;                }                if (ones >= (long)zeros * zeros) {                    ans++;                }            }        }        return ans;    }}

Complexity

Time

O(N^2), where N is the length of the string `s`. The two nested loops iterate through all possible substrings, which are O(N^2) in number. For each substring, the check is an O(1) operation.

Space

O(1), as we only use a few variables to store the counts and the final answer, regardless of the input string size.

Trade-offs

Pros

  • Simple to understand and implement.

Cons

  • Inefficient for large inputs. Given N can be up to 4 * 10^4, N^2 can be up to 1.6 * 10^9, which will lead to a Time Limit Exceeded (TLE) error.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem