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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count the Number of Substrings With Dominant Ones

Number: 3479

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a binary string s, count the number of nonempty substrings that have "dominant ones". A substring is said to have dominant ones if the number of ones in it is greater than or equal to the square of the number of zeros in it.

Key Insights

  • A substring with zero zeros always qualifies since condition becomes ones ≥ 0.
  • For substrings containing k zeros (k ≥ 1), the condition becomes: ones ≥ k². Since substring length = k + ones, the length must be at least k² + k.
  • The quadratic growth of k² means for larger k the condition forces the substring length to be long; in many cases, only substrings with very few zeros can satisfy the condition.
  • By precomputing the positions of zeros and counting substrings that cover a “block” of exactly k zeros, we can “expand” these minimal blocks to the left and right (but not including an extra zero) and count only those extensions that yield a total length L ≥ k²+k.
  • For substrings with no zeros, simply count the contiguous segments of ones.

Space and Time Complexity

Time Complexity: O(n + m * A) where n is the length of s, m is the number of zeros, and A is the average number of left extension choices. In worst-case scenarios (like a dense zeros string) the loops are efficient because most left/right extension counts are small. Space Complexity: O(n) for storing the positions of zeros.

Solution

We solve the problem by splitting it into two parts:

  1. Count all substrings that contain no zeros (these are substrings from continuous segments of ones).
  2. Count all substrings that contain exactly k zeros (for 1 ≤ k ≤ m). For each such substring, determine the minimal block that “must” be included (from the first to the last zero in that block). Then, calculate how many ways we can extend to the left and right while staying within the limits (bound by the position of the previous or next zero) so that the overall length L is at least k²+k.

For a block (i, i+k-1) in the zero-index list:

  • Left extension: the substring can start anywhere from (prev_zero + 1) to zeros[i] (if i==0, prev_zero is -1).
  • Right extension: the substring can end anywhere from zeros[i+k-1] to (next_zero - 1) (if i+k-1 is the last zero then next_zero is n).
  • The minimal block length is given by zeros[i+k-1] - zeros[i] + 1.
  • To satisfy ones ≥ k², i.e. total length L ≥ k²+k, we need additional extension length R such that (base_length + L_ext + R_ext) ≥ k²+k.
  • For each possible left extension length L (from 0 up to left_options-1) we count how many right extension values R (0 to right_options-1) yield L+R ≥ (needed extension) and subtract those invalid pairs from total possibilities.

This method counts each valid substring exactly once without iterating over all O(n²) substrings.

Code Solutions

# Python Solution

def countDominantSubstrings(s: str) -> int:
    n = len(s)
    
    # Count substrings with no zeros. They are formed by contiguous segments of ones.
    count_no_zero = 0
    i = 0
    while i < n:
        if s[i] == '1':
            start = i
            while i < n and s[i] == '1':
                i += 1
            length = i - start
            count_no_zero += (length * (length + 1)) // 2
        else:
            i += 1

    # Precompute indices where s has '0'
    zeros = [i for i, ch in enumerate(s) if ch == '0']
    m = len(zeros)
    count_with_zero = 0

    # Iterate over possible blocks that contain exactly k zeros (k>=1)
    for k in range(1, m + 1):
        # For each consecutive block of k zeros in the zeros list.
        for i in range(0, m - k + 1):
            first_zero = zeros[i]
            last_zero = zeros[i + k - 1]
            base_length = last_zero - first_zero + 1  # minimal block length
            required_total_length = k * k + k          # needed length to have ones  >= k^2
            extra_needed = max(0, required_total_length - base_length)
            
            # Determine how many choices for left extension.
            # The substring cannot extend beyond the previous zero.
            prev_zero = -1 if i == 0 else zeros[i - 1]
            left_options = first_zero - prev_zero  # positions from prev_zero+1 to first_zero inclusive.
            
            # Determine right extension options.
            next_zero = n if (i + k) == m else zeros[i + k]
            right_options = next_zero - last_zero  # positions from last_zero to next_zero-1 inclusive.
            
            total_pairs = left_options * right_options
            invalid_pairs = 0
            # Count number of (L, R) pairs (0-indexed for extra added lengths) with L+R < extra_needed.
            # L can be 0 to left_options-1, R can be 0 to right_options-1.
            for L in range(left_options):
                # For a fixed L, R must be at least (extra_needed - L)
                min_required_R = extra_needed - L
                if min_required_R > 0:
                    # R can only be between 0 and right_options-1.
                    # Count R values that are less than min_required_R.
                    invalid_R = min(right_options, min_required_R)
                    invalid_pairs += invalid_R
            valid_pairs = total_pairs - invalid_pairs
            # If extra_needed > left_options+right_options-2, it means none pair can satisfy L+R >= extra_needed.
            if valid_pairs > 0:
                count_with_zero += valid_pairs
                
    return count_no_zero + count_with_zero

# Example usage:
if __name__ == "__main__":
    s1 = "00011"
    print(countDominantSubstrings(s1))  # Expected output: 5
    s2 = "101101"
    print(countDominantSubstrings(s2))  # Expected output: 16
← Back to All Questions