We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count the Number of Substrings With Dominant Ones

Difficulty: Medium

Problem Description

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.

Key Insights

  • A substring is considered dominant if the count of '1's is >= (count of '0's)².
  • The total number of substrings of a string of length n is n * (n + 1) / 2.
  • Sliding window technique can be useful for counting substrings efficiently.
  • We can maintain a running count of '0's and '1's while expanding or contracting the window.

Space and Time Complexity

Time Complexity: O(n²) in the worst case but can be optimized to O(n) with the right approach.
Space Complexity: O(1) if we do not consider the input storage.

Solution

To solve the problem, we can use a sliding window approach combined with two pointers. We maintain a count of '0's and '1's as we expand our window. When the substring defined by the current window is not dominant, we adjust the left pointer to reduce the window size until it becomes dominant. This way, we can efficiently count all valid substrings.

Code Solutions

def countDominantSubstrings(s: str) -> int:
    n = len(s)
    count = 0
    for start in range(n):
        ones = 0
        zeros = 0
        for end in range(start, n):
            if s[end] == '0':
                zeros += 1
            else:
                ones += 1
            if ones >= zeros * zeros:
                count += 1
    return count
← Back to All Questions