Count Substrings That Satisfy K-Constraint I

Difficulty: Easy | Acceptance: 79.00% | Paid: No Topics: String, Sliding Window

You are given a binary string s and an integer k.

A binary string satisfies the k-constraint if either the number of 0’s in the string is at most k or the number of 1’s in the string is at most k.

Return the number of substrings of s that satisfy the k-constraint.

• Examples
• Constraints
• Brute Force
• Sliding Window

Examples

Example 1:

Input: s = "10101", k = 1
Output: 5
Explanation:
The substrings that satisfy the k-constraint are ["1", "0", "1", "0", "1"].

Example 2:

Input: s = "1010101", k = 2
Output: 10
Explanation:
The substrings that satisfy the k-constraint are ["1", "0", "1", "0", "1", "0", "1", "10", "01", "10"].

Example 3:

Input: s = "11111", k = 2
Output: 15
Explanation:
All substrings satisfy the k-constraint because the number of 1's is at most 2 in all of them.

Constraints

1 <= s.length <= 50
s[i] is either '0' or '1'.
1 <= k <= s.length

Brute Force

Intuition Since the string length is at most 50, we can afford to check every possible substring. We iterate through all start and end indices, count the zeros and ones in that window, and check if the count of either is at most k.

Steps

• Initialize a counter for the result.
• Iterate through the string with index i as the start of the substring.
• Iterate through the string with index j from i to the end as the end of the substring.
• Maintain counts of zeros and ones for the current substring.
• If zeros <= k or ones <= k, increment the result.
• Return the result.

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int) -> int:
        n = len(s)
        ans = 0
        for i in range(n):
            zeros = 0
            ones = 0
            for j in range(i, n):
                if s[j] == '0':
                    zeros += 1
                else:
                    ones += 1
                if zeros <= k or ones <= k:
                    ans += 1
        return ans

Complexity

• Time: O(n²) - We iterate through all possible substrings.
• Space: O(1) - We only use a few variables for counting.
• Notes: Simple and effective given the small constraint (n <= 50).

Sliding Window

Intuition We can optimize the solution using a sliding window approach. For every ending index right, we find the smallest starting index left such that the substring s[left...right] satisfies the k-constraint. All substrings ending at right and starting from 0 to left-1 are valid, but actually, it’s easier to count the valid substrings ending at right by maintaining the window where the constraint is satisfied. If the window violates the constraint (both zeros > k and ones > k), we shrink it from the left until it becomes valid again. The number of valid substrings ending at right is right - left + 1.

Steps

• Initialize left = 0, count0 = 0, count1 = 0, and ans = 0.
• Iterate right from 0 to n - 1:
  • Increment count0 or count1 based on s[right].
  • While count0 > k and count1 > k:
    • Decrement count0 or count1 based on s[left].
    • Increment left.
  • Add right - left + 1 to ans.
• Return ans.

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int) -> int:
        left = 0
        count0 = 0
        count1 = 0
        ans = 0
        for right in range(len(s)):
            if s[right] == '0':
                count0 += 1
            else:
                count1 += 1
            while count0 > k and count1 > k:
                if s[left] == '0':
                    count0 -= 1
                else:
                    count1 -= 1
                left += 1
            ans += right - left + 1
        return ans

Complexity

• Time: O(n) - Each character is added to the window and removed from the window at most once.
• Space: O(1) - We only use a few variables for counting.
• Notes: This is the optimal approach for larger inputs, though for this specific problem (n <= 50), the brute force is also sufficient.