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 Substrings That Satisfy K-Constraint II

Difficulty: Hard

Problem Description

You are given a binary string s and an integer k. You are also given a 2D integer array queries, where queries[i] = [l_i, r_i]. A binary string satisfies the k-constraint if either of the following conditions holds: The number of 0s in the string is at most k, or the number of 1s in the string is at most k. Return an integer array answer, where answer[i] is the number of substrings of s[l_i..r_i] that satisfy the k-constraint.

Key Insights

  • Efficiently counting valid substrings requires careful management of counts of 0s and 1s.
  • Sliding window technique can be utilized to maintain the counts of 0s and 1s within a given range.
  • Prefix sums can help quickly compute the number of valid substrings for different segments of the string.

Space and Time Complexity

Time Complexity: O(n + q * m), where n is the length of the string, q is the number of queries, and m is the maximum length of substrings considered. Space Complexity: O(n), for storing counts and prefix sums.

Solution

To solve the problem, we can use a sliding window approach to count the number of valid substrings within each query range. We will maintain two pointers to represent the current window of the substring, while keeping track of the counts of 0s and 1s. We will iterate through the string and expand the right pointer to include more characters until the substring no longer satisfies the k-constraint. At this point, we will adjust the left pointer and count the valid substrings formed so far.

Code Solutions

def count_substrings(s: str, k: int, queries: List[List[int]]) -> List[int]:
    def count_valid_substrings(start: int, end: int) -> int:
        count_0 = count_1 = 0
        total_substrings = 0
        left = start
        
        for right in range(start, end + 1):
            if s[right] == '0':
                count_0 += 1
            else:
                count_1 += 1
            
            while count_0 > k and count_1 > k:
                if s[left] == '0':
                    count_0 -= 1
                else:
                    count_1 -= 1
                left += 1
            
            total_substrings += (right - left + 1)
        
        return total_substrings

    results = []
    for l, r in queries:
        results.append(count_valid_substrings(l, r))
    
    return results
← Back to All Questions