Count Substrings That Satisfy K-Constraint II - Video Solutions

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.