Skip to main content
Talentd

Count Substrings That Satisfy K-Constraint II - Solution & Explanation

HardArrayStringBinary SearchSliding Window19 min read
Practice this problem

Problem Statement

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:

  • The number of 0's in the string is at most k.
  • The number of 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 <= 105
  • s[i] is either '0' or '1'.
  • 1 <= k <= s.length
  • 1 <= queries.length <= 105
  • queries[i] == [li, ri]
  • 0 <= li <= ri < s.length
  • All queries are distinct.

Approach Overview

Problem 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.

Approach 1: Approach 1: Using Prefix Sums and Sliding Window

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Binary Indexed Tree (Fenwick Tree)

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.

Code

Python

Python

Complexity

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.

Try this approach in the editor →

Approach 3: Sliding Window + Prefix Sum

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n), primarily due to the prefix sums array.

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.
Space Complexity: O(n), due to BIT structures for zeros and ones.

Sliding Window + Prefix Sum—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Prefix Sums + Sliding WindowO(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.

Video Solution

Count Substrings That Satisfy K-Constraint I & II | Detailed Explanation | Leetcode 3258 & 3261 • codestorywithMIK • 8,626 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Count Substrings That Satisfy K-Constraint II easy or hard?
LeetCode classifies this problem as Hard because it mixes substring constraints with multiple range queries. The challenge is recognizing that the sliding window can precompute valid ranges and that prefix sums or Fenwick Trees can convert that information into fast query answers.
Count Substrings That Satisfy K-Constraint II Python/Java solution
Most implementations compute the max valid boundary for each index using a sliding window, then build prefix arrays to answer queries. Python, Java, and C++ solutions follow the same logic: precompute valid ranges, store cumulative counts, and evaluate each query using prefix arithmetic.
How to solve Count Substrings That Satisfy K-Constraint II in O(n)?
Use a sliding window to maintain counts of 0s and 1s while expanding the right pointer. When both counts exceed k, move the left pointer until the substring becomes valid again. Record the maximum valid right boundary for each start index and use prefix sums to compute how many valid substrings fall inside each query interval.
What is the best approach for Count Substrings That Satisfy K-Constraint II?
The most efficient approach combines a sliding window with prefix sums. A two-pointer window determines the farthest valid right boundary for every starting index, ensuring the substring keeps either zeros or ones within k. Prefix sums then aggregate contributions so each query can be answered in constant time after preprocessing.
Is Count Substrings That Satisfy K-Constraint II asked at Google/Amazon/Meta?
Problems combining sliding window preprocessing with range queries are common in interviews at companies like Google, Amazon, and Meta. Variants of substring counting, prefix sum aggregation, and query optimization frequently appear in senior-level algorithm interviews.
What data structure is used in Count Substrings That Satisfy K-Constraint II?
The core solution uses a sliding window with prefix sum arrays for fast query aggregation. An alternative implementation uses a Fenwick Tree (Binary Indexed Tree) to process substring contributions and answer range queries efficiently.
What is the time complexity of Count Substrings That Satisfy K-Constraint II?
The optimal solution runs in O(n + q) time with O(n) space. The sliding window processes each character at most twice to compute valid ranges, and prefix sums allow each query to be answered in O(1). A Fenwick Tree alternative runs in O((n + q) log n).

Ready to solve this problem?

Practice Count Substrings That Satisfy K-Constraint II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays