You are given a binary string s and an integer k.
You are also given a 2D integer array queries, where queries[i] = [li, ri].
A binary string satisfies the k-constraint if either of the following conditions holds:
0's in the string is at most k.1's in the string is at most k.Return an integer array answer, where answer[i] is the number of substrings of s[li..ri] that satisfy the k-constraint.
Example 1:
Input: s = "0001111", k = 2, queries = [[0,6]]
Output: [26]
Explanation:
For the query [0, 6], all substrings of s[0..6] = "0001111" satisfy the k-constraint except for the substrings s[0..5] = "000111" and s[0..6] = "0001111".
Example 2:
Input: s = "010101", k = 1, queries = [[0,5],[1,4],[2,3]]
Output: [15,9,3]
Explanation:
The substrings of s with a length greater than 3 do not satisfy the k-constraint.
Constraints:
1 <= s.length <= 105s[i] is either '0' or '1'.1 <= k <= s.length1 <= queries.length <= 105queries[i] == [li, ri]0 <= li <= ri < s.lengthProblem Overview: You get a binary string s, an integer k, and multiple queries [l, r]. For each query, count how many substrings fully inside the range satisfy the k‑constraint: either the number of 0s or the number of 1s in the substring is at most k.
The brute force idea would check every substring inside each query range and count zeros and ones. That quickly explodes to O(n^2) substrings per query and is unusable for large inputs. The key observation is that the constraint depends only on counts of characters, which can be tracked incrementally with a window.
Approach 1: Prefix Sums and Sliding Window (O(n + q) time, O(n) space)
Use a two‑pointer sliding window to compute the farthest valid right boundary for every starting index. Maintain counts of 0 and 1 while expanding the window. If both counts exceed k, move the left pointer until the substring becomes valid again. This produces an array maxRight[i] representing the largest index where a substring starting at i still satisfies the constraint.
Once these bounds are known, each starting position contributes a fixed number of valid substrings. Build prefix totals so queries can aggregate results quickly. For a query [l, r], substrings starting at i contribute up to min(maxRight[i], r). Precomputed prefix sums from the prefix sum technique allow you to combine contributions in constant time per query.
This approach works because every index is processed at most twice by the sliding window, giving linear preprocessing. Query handling becomes arithmetic on prefix arrays instead of scanning substrings.
Approach 2: Binary Indexed Tree (Fenwick Tree) (O((n + q) log n) time, O(n) space)
Another strategy processes queries offline. After computing maxRight[i], interpret each start index as contributing valid substrings until its boundary. Sort queries by right endpoint and insert contributions gradually while scanning the string. A Fenwick Tree stores partial counts so you can quickly compute how many valid substrings fall inside the query interval.
The Fenwick Tree supports logarithmic updates and range queries. Each insertion represents substrings starting at a position whose valid range is known. Queries retrieve the sum of contributions within [l, r]. This structure is a classic alternative to prefix aggregation when boundaries interact with query limits. Related techniques appear in binary search and range query problems.
Recommended for interviews: The sliding window + prefix sum approach is the expected solution. It demonstrates control of two‑pointer windows, precomputation, and query optimization. Mentioning the brute force idea shows problem understanding, while deriving the linear preprocessing with prefix aggregation shows strong algorithmic intuition.
This approach utilizes prefix sums to quickly fetch the count of 0's and 1's within any substring specified by a query. The prefix sums are computed for zeros and ones separately. Once this preprocessing is done, each query is processed using a sliding window with the help of the prefix sums to count the valid substrings efficiently.
In the Python implementation, we first calculate the prefix sums for both zeros and ones. This allows us to find the count of zeros and ones within any given range efficiently.
For each query, we employ a two-pointer technique (sliding window) to evaluate possible substrings and count those that meet the k-constraint. We expand the right end of the window and check if the substring satisfies the k-constraint. If valid, we calculate how many substrings end with this position and then attempt to expand. We also increment the left pointer when the substring exceeds the k-constraint.
Time Complexity: O(n + q × m), where n is the length of the string, q is the number of queries, and m is the average length of the queried substrings.
Space Complexity: O(n), primarily due to the prefix sums array.
This approach leverages a Binary Indexed Tree (BIT) to efficiently manage and query substring ranges. BIT is useful for dynamic cumulative sum computations, providing optimized point updates and prefix sum queries. This is more complex but beneficial for dynamic ranges where direct sum retrieval is critical.
In this Python code, we define a Fenwick Tree class to manage updates and prefix sum retrievals efficiently for both zeros and ones. We utilize two Fenwick Trees - one to track zeros and another to track ones across indices of the binary string.
For each query, we perform a nested iteration for every starting and ending position, and utilize the BIT to check if the substring is valid according to the k-constraint. This approach, while more sophisticated in its data structure, isn't as efficient as desired due to the single-loop nested within constraints. Optimizations beyond BIT may be required for high density queries.
Python
Time Complexity: O(n log n + q × m log m), where n is the string length, q is the number of queries, and m is the average length of substrings per query.
Space Complexity: O(n), due to BIT structures for zeros and ones.
We use two variables cnt0 and cnt1 to record the number of 0s and 1s in the current window, respectively. Pointers i and j mark the left and right boundaries of the window. We use an array d to record the first position to the right of each position i that does not satisfy the k constraint, initially setting d[i] = n. Additionally, we use a prefix sum array pre[i] of length n + 1 to record the number of substrings that satisfy the k constraint with the right boundary at position i.
When we move the window to the right, if the number of 0s and 1s in the window both exceed k, we update d[i] to j, indicating that the first position to the right of i that does not satisfy the k constraint is j. Then we move i one position to the right until the number of 0s and 1s in the window are both less than or equal to k. At this point, we can calculate the number of substrings that satisfy the k constraint with the right boundary at j, which is j - i + 1, and update this in the prefix sum array.
Finally, for each query [l, r], we first find the first position p to the right of l that does not satisfy the k constraint, which is p = min(r + 1, d[l]). All substrings in the range [l, p - 1] satisfy the k constraint, and the number of such substrings is (1 + p - l) times (p - l) / 2. Then, we calculate the number of substrings that satisfy the k constraint with the right boundary in the range [p, r], which is pre[r + 1] - pre[p]. Finally, we add the two results together.
The time complexity is O(n + m), and the space complexity is O(n). Here, n and m are the lengths of the string s and the query array queries, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Using Prefix Sums and Sliding Window | Time Complexity: O(n + q × m), where n is the length of the string, q is the number of queries, and m is the average length of the queried substrings. |
| Approach 2: Binary Indexed Tree (Fenwick Tree) | Time Complexity: O(n log n + q × m log m), where n is the string length, q is the number of queries, and m is the average length of substrings per query. |
| Sliding Window + Prefix Sum | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Sums + Sliding Window | O(n + q) | O(n) | Best general solution. Precompute valid ranges once and answer queries in constant time. |
| Binary Indexed Tree (Fenwick Tree) | O((n + q) log n) | O(n) | Useful when handling offline queries or when prefix aggregation becomes complex. |
Count Substrings That Satisfy K-Constraint I & II | Detailed Explanation | Leetcode 3258 & 3261 • codestorywithMIK • 8,010 views views
Watch 5 more video solutions →Practice Count Substrings That Satisfy K-Constraint II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor