# Count Substrings That Satisfy K-Constraint II
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-substrings-that-satisfy-k-constraint-ii)
Canonical: https://scaleengineer.com/dsa/problems/count-substrings-that-satisfy-k-constraint-ii
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, String
---
## Problem
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.

# Approaches
## Brute-force Iteration Over Substrings
This is the most straightforward approach. For each query, we iterate through all possible substrings within the given range `[l, r]`. For each of these substrings, we count the number of '0's and '1's to check if it satisfies the k-constraint. To make this slightly more efficient than re-counting for every substring, we can maintain running counts of zeros and ones as we extend the substring from a fixed starting point.
**Time:** O(Q * N^2), where Q is the number of queries and N is the length of the string. For each query, the two nested loops run in O(L^2) where L is the length of the query range (r-l+1), which can be up to N. · **Space:** O(1) extra space, excluding the space for the output array.
**Pros:** Simple to understand and implement.; Requires minimal space.
**Cons:** Extremely inefficient and will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
The brute-force method directly translates the problem statement into code. We are given `Q` queries. For each query `[l, r]`, we need to examine every substring of `s[l..r]`. A substring is defined by its start and end indices. We can use nested loops to generate all such pairs of indices `(i, j)` where `l <= i <= j <= r`.

For each substring `s[i..j]`, we then count the occurrences of '0's and '1's. If the count of '0's is at most `k`, or the count of '1's is at most `k`, we increment a counter for the current query. After checking all substrings for the query `[l, r]`, the value of the counter is our answer for that query.

An optimization is to fix the starting point `i` and extend the endpoint `j`. As `j` increments, we can update the counts of '0's and '1's in `O(1)` time instead of recounting the entire substring `s[i..j]`, which would take `O(j-i+1)` time. This improves the complexity for a single query from `O(L^3)` to `O(L^2)`, where `L` is the length of the query range.

```java
class Solution {
    public long[] countSubstrings(String s, int k, int[][] queries) {
        int q = queries.length;
        long[] ans = new long[q];
        for (int i = 0; i < q; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            long count = 0;
            for (int start = l; start <= r; start++) {
                int zeros = 0;
                int ones = 0;
                for (int end = start; end <= r; end++) {
                    if (s.charAt(end) == '0') {
                        zeros++;
                    } else {
                        ones++;
                    }
                    if (zeros <= k || ones <= k) {
                        count++;
                    }
                }
            }
            ans[i] = count;
        }
        return ans;
    }
}
```
### Algorithm
- For each query `[l, r]` in `queries`:
  - Initialize `valid_count = 0`.
  - Iterate through all possible start indices `i` from `l` to `r`.
    - Initialize `zeros = 0`, `ones = 0`.
    - Iterate through all possible end indices `j` from `i` to `r`.
      - Update `zeros` and `ones` based on `s[j]`.
      - If `zeros <= k` or `ones <= k`, increment `valid_count`.
  - Add `valid_count` to the answer list.

## Precomputation and Linear Scan per Query
This approach improves upon brute-force by using precomputation. Instead of counting valid substrings directly, we count the total number of substrings and subtract the number of *invalid* ones. A substring is invalid if it has more than `k` zeros AND more than `k` ones. The key is to efficiently find, for each starting position `i`, the first ending position `j` that makes the substring `s[i..j]` invalid. This information is precomputed and stored in an array. Then, for each query, we can use this precomputed data to count invalid substrings with a single loop over the query range.
**Time:** O(N + Q*N). The precomputation takes O(N). Each of the Q queries involves a loop of length up to N, leading to a total query time of O(Q*N). · **Space:** O(N) for storing precomputed arrays like `pos0`, `pos1`, `rank0`, `rank1`, and `first_invalid_end`.
**Pros:** Much faster than brute-force due to O(N) precomputation.; The logic of counting invalid substrings is a key insight.
**Cons:** The query processing part is still slow, taking O(N) per query in the worst case.; Will likely time out for large query ranges.
### Explanation
The main idea is to switch from counting valid substrings to counting invalid ones. The total number of substrings in a range `[l, r]` of length `len = r - l + 1` is easily calculated as `len * (len + 1) / 2`.

An invalid substring `s[i..j]` must satisfy `count0(s[i..j]) > k` and `count1(s[i..j]) > k`. For a fixed start `i`, as we increase `j`, the counts of zeros and ones are non-decreasing. This means there's a minimum `j` where the substring `s[i..j]` becomes invalid. Let's call this `first_invalid_end[i]`. Any substring `s[i..p]` with `p >= first_invalid_end[i]` will also be invalid.

We can precompute `first_invalid_end[i]` for all `i` in `O(N)` time. This involves finding the index of the `(k+1)`-th '0' and `(k+1)`-th '1' after position `i`. This is done efficiently using precomputed lists of indices for '0's and '1's (`pos0`, `pos1`) and prefix counts (`rank0`, `rank1`).

Once `first_invalid_end` is computed, we process each query `[l, r]`. We iterate `i` from `l` to `r`. For each `i`, the number of invalid substrings starting at `i` and contained within `s[l..r]` is the number of valid end indices `j` in the range `[first_invalid_end[i], r]`. This count is `max(0, r - first_invalid_end[i] + 1)`. Summing this up for all `i` in `[l, r]` gives the total number of invalid substrings for the query.

```java
class Solution {
    public long[] countSubstrings(String s, int k, int[][] queries) {
        int n = s.length();
        
        List<Integer> pos0 = new ArrayList<>();
        List<Integer> pos1 = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '0') pos0.add(i);
            else pos1.add(i);
        }

        int[] rank0 = new int[n + 1];
        int[] rank1 = new int[n + 1];
        for (int i = 0; i < n; i++) {
            rank0[i+1] = rank0[i] + (s.charAt(i) == '0' ? 1 : 0);
            rank1[i+1] = rank1[i] + (s.charAt(i) == '1' ? 1 : 0);
        }

        int[] firstInvalidEnd = new int[n];
        for (int i = 0; i < n; i++) {
            int targetRank0 = rank0[i] + k;
            int j0 = (targetRank0 < pos0.size()) ? pos0.get(targetRank0) : n;
            
            int targetRank1 = rank1[i] + k;
            int j1 = (targetRank1 < pos1.size()) ? pos1.get(targetRank1) : n;
            
            firstInvalidEnd[i] = Math.max(j0, j1);
        }

        int q = queries.length;
        long[] ans = new long[q];
        for (int i = 0; i < q; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            
            long len = r - l + 1;
            long totalSubstrings = len * (len + 1) / 2;
            long invalidSubstrings = 0;
            
            for (int start = l; start <= r; start++) {
                int invalidStartIdx = firstInvalidEnd[start];
                if (invalidStartIdx <= r) {
                    invalidSubstrings += (r - invalidStartIdx + 1);
                }
            }
            ans[i] = totalSubstrings - invalidSubstrings;
        }
        
        return ans;
    }
}
```
### Algorithm
- **Precomputation:**
  - Compute `pos0`, `pos1` (lists of indices for '0's and '1's) and `rank0`, `rank1` (prefix counts of '0's and '1's). This takes `O(N)`.
  - For each `i` from `0` to `N-1`, calculate `first_invalid_end[i]`, the smallest `j >= i` where `s[i..j]` is invalid. This can be done in `O(1)` for each `i` using the precomputed arrays. Total precomputation time is `O(N)`.
- **Query Processing:**
  - For each query `[l, r]`:
    - Calculate total substrings in `s[l..r]`: `total = len * (len + 1) / 2` where `len = r - l + 1`.
    - Initialize `invalid_substrings = 0`.
    - Iterate `i` from `l` to `r`:
      - The first invalid ending index for a substring starting at `i` is `first_invalid_end[i]`.
      - The number of invalid substrings starting at `i` and ending within `[l,r]` is `max(0, r - first_invalid_end[i] + 1)`.
      - Add this to `invalid_substrings`.
    - The answer for the query is `total_substrings - invalid_substrings`.

## Offline Processing with Fenwick Tree
This approach builds on the previous one to achieve optimal performance. The linear scan per query is the bottleneck. We can optimize the calculation of the sum `sum_{i=l to r} max(0, r - first_invalid_end[i] + 1)` by processing queries offline. Instead of handling queries sequentially, we group them by their right endpoint `r`. We then iterate `r` from `0` to `N-1`, and at each step, we update a data structure (a Fenwick Tree) and answer all queries that end at the current `r`. This turns the 2D-like range query problem into a series of 1D range queries that can be solved efficiently.
**Time:** O(N + (N+Q) log N). Precomputation is O(N). The main loop involves a total of N BIT updates (O(N log N)) and Q BIT queries (O(Q log N)) across all iterations. · **Space:** O(N + Q) for storing precomputed arrays, queries grouped by endpoint, and the Fenwick Trees.
**Pros:** Highly efficient, passing the given constraints.; A standard and powerful technique for a class of offline range query problems.
**Cons:** More complex to understand and implement.; Requires knowledge of Fenwick Trees (or Segment Trees) and the offline processing technique.
### Explanation
The number of invalid substrings for a query `[l, r]` is `sum_{i=l to r, f_i <= r} (r + 1 - f_i)`, where `f_i = first_invalid_end[i]`. This sum can be rewritten as `(r+1) * (count of i in [l,r] with f_i <= r) - (sum of f_i for i in [l,r] with f_i <= r)`.

This is a complex range sum that depends on both `i` and `r`. The offline processing technique elegantly handles this. We sort queries by `r`. As we iterate `r` from `0` to `N-1`, we maintain two Fenwick Trees (BITs). When our sweep line is at `r`, we "activate" all indices `i` for which `f_i = r`. Activating an index `i` means adding its contribution to the BITs: we add `1` to a `bitCount` at position `i`, and we add `f_i` to a `bitSumF` at position `i`.

Now, to answer a query `[l, r]` that ends at our current `r`, we simply query our BITs for the range `[l, r]`. `bitCount.query(l, r)` will give us the count of indices `i` in `[l, r]` such that `f_i <= r` (because only those have been activated so far). Similarly, `bitSumF.query(l, r)` gives the sum of their `f_i` values. With these two values, we can compute the number of invalid substrings in `O(log N)` time.

```java
class FenwickTree {
    private long[] bit;
    private int size;

    public FenwickTree(int size) {
        this.size = size;
        this.bit = new long[size + 1];
    }

    public void add(int index, long value) {
        for (; index <= size; index += index & -index) {
            bit[index] += value;
        }
    }

    public long getSum(int index) {
        long sum = 0;
        for (; index > 0; index -= index & -index) {
            sum += bit[index];
        }
        return sum;
    }
    
    public long query(int l, int r) {
        if (l > r) return 0;
        return getSum(r) - getSum(l - 1);
    }
}

class Solution {
    public long[] countSubstrings(String s, int k, int[][] queries) {
        int n = s.length();
        
        List<Integer> pos0 = new ArrayList<>();
        List<Integer> pos1 = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '0') pos0.add(i); else pos1.add(i);
        }

        int[] rank0 = new int[n + 1];
        int[] rank1 = new int[n + 1];
        for (int i = 0; i < n; i++) {
            rank0[i+1] = rank0[i] + (s.charAt(i) == '0' ? 1 : 0);
            rank1[i+1] = rank1[i] + (s.charAt(i) == '1' ? 1 : 0);
        }

        int[] firstInvalidEnd = new int[n];
        List<List<Integer>> indicesByF = new ArrayList<>(n + 1);
        for(int i = 0; i <= n; i++) indicesByF.add(new ArrayList<>());

        for (int i = 0; i < n; i++) {
            int targetRank0 = rank0[i] + k;
            int j0 = (targetRank0 < pos0.size()) ? pos0.get(targetRank0) : n;
            int targetRank1 = rank1[i] + k;
            int j1 = (targetRank1 < pos1.size()) ? pos1.get(targetRank1) : n;
            firstInvalidEnd[i] = Math.max(j0, j1);
            if (firstInvalidEnd[i] <= n) {
                indicesByF.get(firstInvalidEnd[i]).add(i);
            }
        }

        int q = queries.length;
        List<List<int[]>> queriesByR = new ArrayList<>(n);
        for(int i = 0; i < n; i++) queriesByR.add(new ArrayList<>());
        for (int i = 0; i < q; i++) {
            queriesByR.get(queries[i][1]).add(new int[]{queries[i][0], i});
        }

        FenwickTree bitCount = new FenwickTree(n);
        FenwickTree bitSumF = new FenwickTree(n);
        long[] ans = new long[q];

        for (int r = 0; r < n; r++) {
            if (r < indicesByF.size()) {
                for (int i : indicesByF.get(r)) {
                    bitCount.add(i + 1, 1);
                    bitSumF.add(i + 1, firstInvalidEnd[i]);
                }
            }

            for (int[] query : queriesByR.get(r)) {
                int l = query[0];
                int qIdx = query[1];

                long countActive = bitCount.query(l + 1, r + 1);
                long sumF = bitSumF.query(l + 1, r + 1);
                long invalidCount = (long)(r + 1) * countActive - sumF;
                
                long len = r - l + 1;
                long totalSubstrings = len * (len + 1) / 2;
                ans[qIdx] = totalSubstrings - invalidCount;
            }
        }
        
        return ans;
    }
}
```
### Algorithm
- **Precomputation:**
  - Same as Approach 2, compute `first_invalid_end[i]` for all `i`. Let `f_i = first_invalid_end[i]`. `O(N)`.
  - Group all starting indices `i` by their `f_i` value into a list of lists, `indicesByF`. `O(N)`.
- **Offline Processing:**
  - Group all queries by their right endpoint `r` into `queriesByR`. `O(Q)`.
  - Initialize two Fenwick Trees (BITs), `bitCount` and `bitSumF`, of size `N`. `O(N)`.
  - Initialize an answer array `ans`. `O(Q)`.
  - Loop `r` from `0` to `N-1`:
    - For each index `i` in `indicesByF[r]` (i.e., `f_i == r`):
      - "Activate" this index `i` by updating the BITs: `bitCount.add(i+1, 1)` and `bitSumF.add(i+1, f_i)`.
    - For each query `(l, q_idx)` in `queriesByR[r]`:
      - Query the BITs to get the count of active indices and the sum of their `f` values in the range `[l, r]`: `count = bitCount.query(l+1, r+1)` and `sumF = bitSumF.query(l+1, r+1)`.
      - Calculate invalid substrings: `invalid = (long)(r + 1) * count - sumF`.
      - Calculate total substrings and find the final answer: `ans[q_idx] = total - invalid`.

# Solutions
### Java

```java
class Solution {
public
  long[] countKConstraintSubstrings(String s, int k, int[][] queries) {
    int[] cnt = new int[2];
    int n = s.length();
    int[] d = new int[n];
    Arrays.fill(d, n);
    long[] pre = new long[n + 1];
    for (int i = 0, j = 0; j < n; ++j) {
      cnt[s.charAt(j) - '0']++;
      while (cnt[0] > k && cnt[1] > k) {
        d[i] = j;
        cnt[s.charAt(i++) - '0']--;
      }
      pre[j + 1] = pre[j] + j - i + 1;
    }
    int m = queries.length;
    long[] ans = new long[m];
    for (int i = 0; i < m; ++i) {
      int l = queries[i][0], r = queries[i][1];
      int p = Math.min(r + 1, d[l]);
      long a = (1L + p - l) * (p - l) / 2;
      long b = pre[r + 1] - pre[p];
      ans[i] = a + b;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<long long> countKConstraintSubstrings(string s, int k,
                                               vector<vector<int>> &queries) {
    int cnt[2]{};
    int n = s.size();
    vector<int> d(n, n);
    long long pre[n + 1];
    pre[0] = 0;
    for (int i = 0, j = 0; j < n; ++j) {
      cnt[s[j] - '0']++;
      while (cnt[0] > k && cnt[1] > k) {
        d[i] = j;
        cnt[s[i++] - '0']--;
      }
      pre[j + 1] = pre[j] + j - i + 1;
    }
    vector<long long> ans;
    for (const auto &q : queries) {
      int l = q[0], r = q[1];
      int p = min(r + 1, d[l]);
      long long a = (1LL + p - l) * (p - l) / 2;
      long long b = pre[r + 1] - pre[p];
      ans.push_back(a + b);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countKConstraintSubstrings(self, s: str, k: int, queries: List[List[int]]) -> List[int]: cnt = [0, 0] i, n = 0, len(s) d = [n] * n pre = [0] * (n + 1) for j, x in enumerate(map(int, s)): cnt[x] += 1 while cnt[0] > k and cnt[1] > k: d[i] = j cnt[int(s[i])] -= 1 i += 1 pre[j + 1] = pre[j] + j - i + 1 ans = [] for l, r in queries: p = min(r + 1, d[l]) a = (1 + p - l) * (p - l) // 2 b = pre[r + 1] - pre[p] ans . append(a + b) return ans

```