Problem Description

You are given a binary string s consisting of 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)

You are also given a 2D integer array queries, where each queries[i] = [li, ri] represents a query asking about a specific substring s[li..ri] (inclusive).

For each query, you need to count how many substrings within s[li..ri] satisfy the k-constraint.

Your task is to return an integer array answer, where answer[i] is the number of substrings of s[li..ri] that satisfy the k-constraint.

Example: If s = "0011", k = 1, and queries = [[0, 3]]:

• We need to find all substrings of s[0..3] = "0011" that satisfy the k-constraint
• Valid substrings include: "0" (at index 0), "0" (at index 1), "1" (at index 2), "1" (at index 3), "00", "01", "11"
• Each of these has either at most 1 zero or at most 1 one
• Invalid substrings: "001", "011", "0011" (these have both more than 1 zero AND more than 1 one)

Intuition

The key insight is that we need to efficiently count valid substrings for multiple queries over different ranges. A naive approach of checking every substring for every query would be too slow.

Let's think about what makes a substring valid: it needs to have either at most k zeros OR at most k ones. This means a substring becomes invalid only when it has BOTH more than k zeros AND more than k ones.

For any starting position i, there exists a critical position where substrings starting at i transition from valid to invalid as we extend to the right. Once we hit a position j where the substring s[i..j] has more than k zeros AND more than k ones, all longer substrings starting at i will also be invalid.

This observation leads us to use a sliding window approach. As we expand the window to the right, we track when the window becomes invalid (having more than k of both 0s and 1s). When this happens, we need to shrink from the left until it's valid again.

For each starting position i, we can precompute the first position d[i] where the substring becomes invalid. This means all substrings s[i..j] where j < d[i] are valid.

To handle queries efficiently, we also need to precompute the count of valid substrings ending at each position using a prefix sum array. For position j, the number of valid substrings ending at j equals the number of valid starting positions, which is j - i + 1 where i is the leftmost valid starting position.

When answering a query [l, r], we split it into two parts:

1. Substrings starting at l that remain valid throughout (from l to min(r+1, d[l])-1)
2. Substrings that start after l and end within the query range

The first part forms a continuous range where all substrings are valid, giving us (1 + p - l) * (p - l) / 2 substrings. The second part can be calculated using our prefix sum array as pre[r+1] - pre[p].

Learn more about Binary Search, Prefix Sum and Sliding Window patterns.

Solution Approach

The solution uses a sliding window technique combined with prefix sums to efficiently handle multiple queries.

Step 1: Initialize Data Structures

• cnt = [0, 0]: Track count of 0s and 1s in current window
• i = 0: Left boundary of sliding window
• d = [n] * n: Array where d[i] stores the first position to the right of i that doesn't satisfy k-constraint (initialized to n)
• pre = [0] * (n + 1): Prefix sum array where pre[j+1] stores total count of valid substrings ending at or before position j

Step 2: Build the Sliding Window and Precompute Values For each position j from 0 to n-1:

1. Add character at position j to the window: cnt[int(s[j])] += 1
2. Check if window violates k-constraint: cnt[0] > k and cnt[1] > k
3. If violated, shrink window from left:
   • Record d[i] = j (position j is first invalid position for starting index i)
   • Remove leftmost character: cnt[int(s[i])] -= 1
   • Move left boundary: i += 1
   • Repeat until window satisfies k-constraint
4. Count valid substrings ending at j: j - i + 1 (all starting positions from i to j form valid substrings)
5. Update prefix sum: pre[j + 1] = pre[j] + j - i + 1

Step 3: Answer Queries For each query [l, r]:

1. Find the boundary: p = min(r + 1, d[l])

   • p is the first position where substrings starting at l become invalid
   • If d[l] > r + 1, all substrings in range are valid

2. Calculate valid substrings in two parts:

   • Part A: Substrings starting at l and ending before p
     • These form all possible substrings from position l to p-1
     • Count: a = (1 + p - l) * (p - l) // 2
     • This is the formula for sum of integers from 1 to (p - l)
   • Part B: Valid substrings with right boundary in range [p, r]
     • Use prefix sum difference: b = pre[r + 1] - pre[p]
     • This gives count of all valid substrings ending between positions p and r

3. Total count for query: a + b

Time Complexity: O(n + q) where n is string length and q is number of queries

• Preprocessing takes O(n) with single pass
• Each query answered in O(1) using precomputed values

Space Complexity: O(n) for storing arrays d and pre

Example Walkthrough

Let's walk through a concrete example with s = "0011", k = 1, and queries = [[0, 3]].

Step 1: Initialize

• n = 4, cnt = [0, 0] (tracks count of 0s and 1s)
• i = 0 (left boundary of sliding window)
• d = [4, 4, 4, 4] (initially all set to n=4)
• pre = [0, 0, 0, 0, 0] (prefix sum array with n+1 elements)

Step 2: Build Sliding Window

Process j = 0 (s[0] = '0'):

• Add '0' to window: cnt = [1, 0]
• Check constraint: cnt[0] = 1 ≤ k and cnt[1] = 0 ≤ k ✓ (valid)
• Valid substrings ending at 0: 0 - 0 + 1 = 1 (substring "0")
• Update: pre[1] = pre[0] + 1 = 1

Process j = 1 (s[1] = '0'):

• Add '0' to window: cnt = [2, 0]
• Check constraint: cnt[0] = 2 > k but cnt[1] = 0 ≤ k ✓ (still valid, needs only ONE condition)
• Valid substrings ending at 1: 1 - 0 + 1 = 2 (substrings "0", "00")
• Update: pre[2] = pre[1] + 2 = 3

Process j = 2 (s[2] = '1'):

• Add '1' to window: cnt = [2, 1]
• Check constraint: cnt[0] = 2 > k and cnt[1] = 1 ≤ k ✓ (still valid)
• Valid substrings ending at 2: 2 - 0 + 1 = 3 (substrings "1", "01", "001")
• Update: pre[3] = pre[2] + 3 = 6

Process j = 3 (s[3] = '1'):

• Add '1' to window: cnt = [2, 2]
• Check constraint: cnt[0] = 2 > k AND cnt[1] = 2 > k ✗ (INVALID!)
• Window violates k-constraint, must shrink:
  • Record d[0] = 3 (position 3 is first invalid for starting index 0)
  • Remove s[0] = '0': cnt = [1, 2], i = 1
  • Still invalid: cnt[0] = 1 ≤ k but cnt[1] = 2 > k ✓ (now valid!)
• Valid substrings ending at 3: 3 - 1 + 1 = 3 (substrings "1", "11", "011")
• Update: pre[4] = pre[3] + 3 = 9

Final arrays:

• d = [3, 4, 4, 4] (d[0]=3 means substrings starting at 0 become invalid at position 3)
• pre = [0, 1, 3, 6, 9]

Step 3: Answer Query [0, 3]

For query [l=0, r=3]:

1. Find boundary: p = min(r + 1, d[l]) = min(4, 3) = 3

2. Calculate Part A (substrings starting at 0, ending before 3):

   • These are substrings from position 0 to 2
   • Count: a = (1 + 3 - 0) * (3 - 0) // 2 = 4 * 3 // 2 = 6
   • These are: "0" (length 1), "00" (length 2), "001" (length 3)

3. Calculate Part B (valid substrings ending in range [3, 3]):

   • b = pre[4] - pre[3] = 9 - 6 = 3
   • These are the valid substrings ending at position 3: "1", "11", "011"

4. Total: a + b = 6 + 3 = 9

The answer correctly identifies 9 valid substrings:

• Starting at 0: "0", "00", "001" (3 substrings)
• Starting at 1: "0", "01", "011" (3 substrings)
• Starting at 2: "1", "11" (2 substrings)
• Starting at 3: "1" (1 substring)

Note that "0011" is invalid because it has 2 zeros AND 2 ones (both > k=1).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m)

The algorithm consists of two main phases:

1. Preprocessing phase: The first loop iterates through the string s once with a two-pointer technique. Although there's a nested while loop, each character is visited at most twice (once by pointer j and once by pointer i). This gives us O(n) time.

2. Query processing phase: The second loop processes each query in constant time O(1) by using the precomputed arrays d and pre. With m queries, this phase takes O(m) time.

Therefore, the total time complexity is O(n + m).

Space Complexity: O(n)

The algorithm uses several auxiliary data structures:

• cnt: array of size 2, which is O(1)
• d: array of size n, which is O(n)
• pre: array of size n + 1, which is O(n)
• ans: array to store results of size m, which is O(m)

Since the output array ans is typically not counted in space complexity analysis (as it's required for the output), the dominant space usage comes from arrays d and pre, giving us O(n) space complexity.

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

Common Pitfalls

1. Incorrect Boundary Calculation for Queries

A common mistake is misunderstanding what right_boundary[i] represents and how to use it in query processing. Developers might incorrectly assume all substrings starting at query_left and ending anywhere in [query_left, query_right] are valid if right_boundary[query_left] > query_right.

Wrong approach:

# Incorrect: Assuming all substrings are valid if boundary exceeds query range
if right_boundary[query_left] > query_right:
    result.append((query_right - query_left + 1) * (query_right - query_left + 2) // 2)

Correct approach:

# Must still split into two parts even when boundary exceeds range
boundary_point = min(query_right + 1, right_boundary[query_left])
substrings_before_boundary = (1 + boundary_point - query_left) * (boundary_point - query_left) // 2
substrings_after_boundary = prefix_sum[query_right + 1] - prefix_sum[boundary_point]

2. Off-by-One Errors in Prefix Sum Array

The prefix sum array uses 1-based indexing (prefix_sum[j+1] stores sum up to index j), which can lead to indexing errors.

Wrong approach:

# Incorrect indexing
prefix_sum[right] = prefix_sum[right - 1] + (right - left + 1)  # Wrong!
substrings_after_boundary = prefix_sum[query_right] - prefix_sum[boundary_point - 1]  # Wrong!

Correct approach:

# Proper 1-based indexing for prefix sum
prefix_sum[right + 1] = prefix_sum[right] + (right - left + 1)
substrings_after_boundary = prefix_sum[query_right + 1] - prefix_sum[boundary_point]

3. Misunderstanding the K-Constraint Condition

The k-constraint is satisfied if either condition is met (at most k zeros OR at most k ones), not both. The violation occurs only when both counts exceed k.

Wrong approach:

# Incorrect: Treating it as AND condition
while count[0] > k or count[1] > k:  # Wrong! Too restrictive
    right_boundary[left] = right
    count[int(s[left])] -= 1
    left += 1

Correct approach:

# Correct: Window violates constraint only when BOTH exceed k
while count[0] > k and count[1] > k:
    right_boundary[left] = right
    count[int(s[left])] -= 1
    left += 1

4. Integer Overflow in Substring Count Formula

When calculating the number of substrings, the formula (1 + p - l) * (p - l) // 2 can cause integer overflow for large values, though this is more relevant in languages like C++ than Python.

Prevention in Python:

# Python handles large integers automatically, but for other languages:
# Use appropriate data types (long long in C++) or modular arithmetic if required
substrings_before_boundary = (1 + boundary_point - query_left) * (boundary_point - query_left) // 2

5. Not Initializing right_boundary Correctly

Failing to initialize right_boundary array to n can cause incorrect results for positions where the window never violates the constraint.

Wrong approach:

right_boundary = [0] * n  # Wrong! Should be initialized to n

Correct approach:

right_boundary = [n] * n  # Correct: Default to string end if never violated