#3234

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Count the Number of Substrings With Dominant Ones

Count the number of substrings in a binary string with dominant ones, using a sliding window approach with state updates.

string sliding window enumeration

Problem Statement

You are given a binary string s. A substring has dominant ones if the number of ones in it is greater than or equal to the square of the number of zeros.

Return the number of substrings in s that meet this condition. Use an efficient method to explore all possible substrings, leveraging a sliding window with running state updates.

Examples

Example 1

Input: s = "00011"

Output: 5

The substrings with dominant ones are shown in the table below.

Example 2

Input: s = "101101"

Output: 16

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.

Constraints

1 <= s.length <= 4 * 104
s consists only of characters '0' and '1'.

Solution Approach

Sliding Window with Running State Updates

Fix the starting index l of the substring, and use a sliding window approach to iterate over possible end indices r. For each pair (l, r), check if the number of ones is greater than or equal to the square of zeros within that substring.

Efficient Substring Counting

Track the number of ones and zeros dynamically as the window expands. Whenever the window contains dominant ones, count all substrings from the current l to r and move to the next index l.

Handling Edge Cases

Consider edge cases where the string contains only zeros or ones. These scenarios should be handled efficiently by the sliding window without unnecessary recalculation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the sliding window approach and how efficiently we update the counts for ones and zeros. In the best case, the algorithm may achieve linear time, while the space complexity depends on the method of state tracking used for the sliding window, typically O(n).

What Interviewers Usually Probe

Look for familiarity with the sliding window technique.
Expect the candidate to handle edge cases like all zeros or all ones efficiently.
The ability to explain time and space complexity in the context of the sliding window pattern is crucial.

Common Pitfalls or Variants

Common pitfalls

Not updating the running count of ones and zeros correctly within the window.
Over-complicating the approach, leading to a higher time complexity than necessary.
Failing to account for all valid substrings when determining the count.

Follow-up variants

Count substrings with dominant ones in a binary string with additional constraints, such as specific length or pattern restrictions.
Use a more optimized version of the sliding window algorithm to reduce space complexity.
Expand the problem to consider substrings with dominant ones in non-binary strings, applying a similar sliding window approach.

FAQ

What is the sliding window approach for the 'Count the Number of Substrings With Dominant Ones' problem?

The sliding window approach for this problem involves fixing a starting index and expanding the window until the substring has dominant ones. You dynamically update counts of ones and zeros as the window grows.

How do I optimize counting substrings in this problem?

Optimizing the counting involves using a sliding window to count substrings with dominant ones dynamically. This method reduces the need for checking all possible substrings individually.

What edge cases should I handle when solving this problem?

Handle cases with strings containing only zeros or only ones, as these represent extreme conditions that can affect the validity of the dominant ones rule.

How does GhostInterview help with the 'Count the Number of Substrings With Dominant Ones' problem?

GhostInterview guides you through the sliding window technique, helping you break down the problem and avoid pitfalls while improving both time and space efficiency.

What time complexity can I expect from the sliding window solution for this problem?

The time complexity depends on how efficiently the sliding window is implemented. Typically, it will be linear, O(n), but careful tracking of the counts is needed to achieve this.

terminal

Solution

Solution 1: Preprocessing + Enumeration

According to the problem description, a dominant string satisfies $\textit{cnt}_1 \geq \textit{cnt}_0^2$, which means the maximum value of $\textit{cnt}_0$ does not exceed $\sqrt{n}$, where $n$ is the length of the string. Therefore, we can enumerate the value of $\textit{cnt}_0$ and then calculate the number of substrings that satisfy the condition.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        n = len(s)
        nxt = [n] * (n + 1)
        for i in range(n - 1, -1, -1):
            nxt[i] = nxt[i + 1]
            if s[i] == "0":
                nxt[i] = i
        ans = 0
        for i in range(n):
            cnt0 = int(s[i] == "0")
            j = i
            while j < n and cnt0 * cnt0 <= n:
                cnt1 = (nxt[j + 1] - i) - cnt0
                if cnt1 >= cnt0 * cnt0:
                    ans += min(nxt[j + 1] - j, cnt1 - cnt0 * cnt0 + 1)
                j = nxt[j + 1]
                cnt0 += 1
        return ans

Continue Practicing

#3445 maximum difference between even and odd frequency ii #3258 count substrings that satisfy k constraint i #3261 count substrings that satisfy k constraint ii