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

Number: 3543

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given a binary string s and an integer k, we need to count the number of non-empty substrings such that the substring satisfies the k-constraint. A substring satisfies the k-constraint if either the number of 0's in it is at most k or the number of 1's in it is at most k.

Key Insights

  • The string only contains characters '0' and '1', and its maximum length is 50, so an O(n²) brute force approach is acceptable.
  • A substring satisfies the k-constraint if at least one of its character counts (zeros or ones) is ≤ k.
  • By iterating over all possible substrings and updating counts as we extend the substring, we can decide whether each substring satisfies the given constraint.
  • Although advanced sliding window techniques exist, here a straightforward nested loop with counters is simple and efficient due to the small constraints.

Space and Time Complexity

Time Complexity: O(n²), where n is the length of the string. Space Complexity: O(1), as only a few integer counters are maintained.

Solution

The solution iterates over every possible substring by using two nested loops. For each substring, we maintain running counts for 0's and 1's. If either count remains less than or equal to k, the substring is valid and we increment our count. This approach avoids recalculating the character counts for each substring from scratch by updating them as the substring extends.

Code Solutions

# Python solution with detailed comments
def countSubstringsKConstraint(s: str, k: int) -> int:
    n = len(s)
    count_valid = 0
    # Iterate over all starting indices of substrings.
    for i in range(n):
        zeros = 0
        ones = 0
        # Extend the substring from index i to j.
        for j in range(i, n):
            # Update counts based on the current character.
            if s[j] == '0':
                zeros += 1
            else:
                ones += 1
            # Check if the substring satisfies the k-constraint.
            if zeros <= k or ones <= k:
                count_valid += 1
    return count_valid

# Example usage:
print(countSubstringsKConstraint("10101", 1))  # Expected output: 12
← Back to All Questions