Problem Description

You are given a binary string s (containing only '0's and '1's) and an integer k.

A binary string satisfies the k-constraint if at least one of these conditions is true:

• The string contains at most k zeros (0's)
• The string contains at most k ones (1's)

Your task is to count how many substrings of s satisfy the k-constraint.

For example, if s = "10101" and k = 1:

• Substring "1" satisfies the k-constraint (0 zeros, 1 one)
• Substring "0" satisfies the k-constraint (1 zero, 0 ones)
• Substring "10" satisfies the k-constraint (1 zero, 1 one)
• Substring "101" does NOT satisfy the k-constraint (1 zero, 2 ones - both counts exceed k)

The solution uses a sliding window approach. It maintains a window [l, r] and tracks the count of 0's and 1's in the current window using cnt[0] and cnt[1]. For each position r, it:

1. Adds the character at position r to the window
2. Shrinks the window from the left (incrementing l) while both counts exceed k
3. Once the window satisfies the k-constraint, all substrings ending at position r and starting from any position between l and r are valid, contributing r - l + 1 substrings to the answer

The algorithm efficiently counts all valid substrings in O(n) time by recognizing that if a window [l, r] satisfies the k-constraint, then all its suffixes ending at r also satisfy the constraint.

Intuition

The key insight is recognizing that if a substring satisfies the k-constraint, then all of its substrings also satisfy the k-constraint. Conversely, if a substring violates the k-constraint (having more than k zeros AND more than k ones), then any substring containing it will also violate the constraint.

This property suggests using a sliding window approach. We can maintain a window that always satisfies the k-constraint and count all valid substrings ending at each position.

Consider what happens as we expand our window to the right by including a new character:

• If the window still satisfies the k-constraint, great! We've found more valid substrings.
• If the window now violates the k-constraint (both counts exceed k), we need to shrink from the left until it's valid again.

The clever counting trick comes from realizing that for a valid window [l, r], we don't need to check every possible substring individually. Instead, we know that all substrings ending at position r and starting anywhere from l to r are valid. That gives us exactly r - l + 1 valid substrings ending at position r.

Why does this work? Because if the entire window [l, r] satisfies the k-constraint (at least one count ≤ k), then any smaller window within it will have even smaller counts, thus also satisfying the constraint.

This approach avoids the naive O(n²) or O(n³) solution of checking every possible substring. By maintaining a valid window and using the counting trick, we process each character exactly once, achieving O(n) time complexity.

Learn more about Sliding Window patterns.

Solution Approach

The solution implements a sliding window technique with two pointers to efficiently count all valid substrings.

Data Structures Used:

• cnt = [0, 0]: An array to track the count of 0's and 1's in the current window. cnt[0] stores the count of 0's, and cnt[1] stores the count of 1's.
• l: Left pointer of the sliding window, initially at position 0.
• ans: Accumulator for the total count of valid substrings.

Algorithm Steps:

1. Initialize the window: Start with an empty window where l = 0 and counts are [0, 0].

2. Expand the window: Iterate through the string with the right pointer r. For each character:

   • Convert the character to an integer ('0' → 0, '1' → 1)
   • Increment the corresponding count: cnt[x] += 1

3. Shrink if necessary: After adding a new character, check if the window violates the k-constraint:

   while cnt[0] > k and cnt[1] > k:
       cnt[int(s[l])] -= 1
       l += 1

   This loop continues shrinking the window from the left until at least one count becomes ≤ k.

4. Count valid substrings: Once the window [l, r] is valid, all substrings ending at position r are valid. The number of such substrings is r - l + 1:

   • Substring from position l to r (length: r - l + 1)
   • Substring from position l + 1 to r (length: r - l)
   • ...
   • Substring from position r to r (length: 1)

5. Accumulate the result: Add r - l + 1 to ans for each valid window state.

Time Complexity: O(n) where n is the length of the string. Each character is visited at most twice (once by the right pointer, once by the left pointer).

Space Complexity: O(1) as we only use a fixed amount of extra space regardless of input size.

Example Walkthrough

Let's trace through the algorithm with s = "11010" and k = 1.

Initial State:

• l = 0, ans = 0, cnt = [0, 0] (counts for 0's and 1's)

Step 1: r = 0, character = '1'

• Add '1' to window: cnt = [0, 1]
• Check constraint: cnt[0] = 0 ≤ 1 ✓ (satisfies k-constraint)
• Valid substrings ending at position 0: r - l + 1 = 0 - 0 + 1 = 1
  • "1" (from index 0 to 0)
• ans = 0 + 1 = 1

Step 2: r = 1, character = '1'

• Add '1' to window: cnt = [0, 2]
• Check constraint: cnt[0] = 0 ≤ 1 ✓ (satisfies k-constraint)
• Valid substrings ending at position 1: r - l + 1 = 1 - 0 + 1 = 2
  • "11" (from index 0 to 1)
  • "1" (from index 1 to 1)
• ans = 1 + 2 = 3

Step 3: r = 2, character = '0'

• Add '0' to window: cnt = [1, 2]
• Check constraint: cnt[0] = 1 ≤ 1 ✓ (satisfies k-constraint)
• Valid substrings ending at position 2: r - l + 1 = 2 - 0 + 1 = 3
  • "110" (from index 0 to 2)
  • "10" (from index 1 to 2)
  • "0" (from index 2 to 2)
• ans = 3 + 3 = 6

Step 4: r = 3, character = '1'

• Add '1' to window: cnt = [1, 3]
• Check constraint: cnt[0] = 1 ≤ 1 ✓ (satisfies k-constraint)
• Valid substrings ending at position 3: r - l + 1 = 3 - 0 + 1 = 4
  • "1101" (from index 0 to 3)
  • "101" (from index 1 to 3)
  • "01" (from index 2 to 3)
  • "1" (from index 3 to 3)
• ans = 6 + 4 = 10

Step 5: r = 4, character = '0'

• Add '0' to window: cnt = [2, 3]
• Check constraint: Both cnt[0] = 2 > 1 and cnt[1] = 3 > 1 ✗ (violates k-constraint)
• Shrink window:
  • Remove s[0] = '1': cnt = [2, 2], l = 1
  • Still violates (both > 1), continue shrinking
  • Remove s[1] = '1': cnt = [2, 1], l = 2
  • Now cnt[1] = 1 ≤ 1 ✓ (satisfies k-constraint)
• Valid substrings ending at position 4: r - l + 1 = 4 - 2 + 1 = 3
  • "010" (from index 2 to 4)
  • "10" (from index 3 to 4)
  • "0" (from index 4 to 4)
• ans = 10 + 3 = 13

Final Answer: 13

The algorithm efficiently counted all 13 valid substrings by maintaining a sliding window that always satisfies the k-constraint, avoiding the need to check each substring individually.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string s.

The algorithm uses a sliding window approach with two pointers (l and r). The right pointer r iterates through each character in the string exactly once in the for loop. The left pointer l moves forward in the while loop, but each position in the string is visited by l at most once throughout the entire execution. Since each element is processed at most twice (once by r and once by l), and all operations inside the loops (array access, addition, subtraction) are O(1), the overall time complexity is O(n).

Space Complexity: O(1)

The algorithm uses a fixed amount of extra space:

• cnt: an array of size 2 to track the count of 0s and 1s in the current window
• ans, l, r, x: integer variables for storing the result and pointers

Since the space usage doesn't grow with the input size and remains constant regardless of the length of string s, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Window Validity Contribution

The Mistake: A common error is thinking that when we have a valid window [l, r], we should only count it as one valid substring. This leads to incorrect code like:

# INCORRECT approach
for right in range(len(s)):
    count[int(s[right])] += 1
  
    while count[0] > k and count[1] > k:
        count[int(s[left])] -= 1
        left += 1
  
    result += 1  # Wrong! Only counts one substring per position

Why It's Wrong: When the window [l, r] satisfies the k-constraint, ALL substrings ending at position r are valid. This includes:

• The substring from l to r
• The substring from l+1 to r
• The substring from l+2 to r
• ... up to the substring from r to r (single character)

The Fix: Add right - left + 1 to the result, which counts all valid substrings ending at the current position:

result += right - left + 1  # Correct: counts all valid substrings ending at r

Pitfall 2: Incorrect Window Shrinking Condition

The Mistake: Using OR instead of AND in the shrinking condition:

# INCORRECT: shrinks too aggressively
while count[0] > k or count[1] > k:
    count[int(s[left])] -= 1
    left += 1

Why It's Wrong: The k-constraint is satisfied when EITHER the count of 0s is ≤ k OR the count of 1s is ≤ k. We only need to shrink when BOTH counts exceed k. Using OR would shrink the window even when it's still valid, missing many valid substrings.

Example: For s = "110" and k = 1:

• After processing "11", we have count = [0, 2]
• With OR condition: window shrinks (since count[1] > k)
• With AND condition: window doesn't shrink (since count[0] ≤ k)
• The substring "11" is actually valid because it has 0 zeros (≤ k)

The Fix: Use AND to ensure we only shrink when both conditions are violated:

while count[0] > k and count[1] > k:  # Correct: only shrink when both exceed k

Pitfall 3: Off-by-One Error in Counting

The Mistake: Using right - left instead of right - left + 1:

# INCORRECT: misses counting some substrings
result += right - left

Why It's Wrong: The number of substrings ending at position r and starting anywhere from l to r is r - l + 1, not r - l. For example, if l = 2 and r = 4, there are 3 valid substrings: [2,4], [3,4], and [4,4].

The Fix: Always add 1 to account for all positions from l to r inclusive:

result += right - left + 1  # Correct formula