<p>You are given a <strong>binary</strong> string <code>s</code> and an integer <code>k</code>.</p>

<p>You are also given a 2D integer array <code>queries</code>, where <code>queries[i] = [l<sub>i</sub>, r<sub>i</sub>]</code>.</p>

<p>A <strong>binary string</strong> satisfies the <strong>k-constraint</strong> if <strong>either</strong> of the following conditions holds:</p>

<ul>
	<li>The number of <code>0</code>&#39;s in the string is at most <code>k</code>.</li>
	<li>The number of <code>1</code>&#39;s in the string is at most <code>k</code>.</li>
</ul>

<p>Return an integer array <code>answer</code>, where <code>answer[i]</code> is the number of <span data-keyword="substring-nonempty">substrings</span> of <code>s[l<sub>i</sub>..r<sub>i</sub>]</code> that satisfy the <strong>k-constraint</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;0001111&quot;, k = 2, queries = [[0,6]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[26]</span></p>

<p><strong>Explanation:</strong></p>

<p>For the query <code>[0, 6]</code>, all substrings of <code>s[0..6] = &quot;0001111&quot;</code> satisfy the k-constraint except for the substrings <code>s[0..5] = &quot;000111&quot;</code> and <code>s[0..6] = &quot;0001111&quot;</code>.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;010101&quot;, k = 1, queries = [[0,5],[1,4],[2,3]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[15,9,3]</span></p>

<p><strong>Explanation:</strong></p>

<p>The substrings of <code>s</code> with a length greater than 3 do not satisfy the k-constraint.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s[i]</code> is either <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
	<li><code>1 &lt;= k &lt;= s.length</code></li>
	<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>
	<li><code>queries[i] == [l<sub>i</sub>, r<sub>i</sub>]</code></li>
	<li><code>0 &lt;= l<sub>i</sub> &lt;= r<sub>i</sub> &lt; s.length</code></li>
	<li>All queries are distinct.</li>
</ul>

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int, queries: list[list[int]]) -> list[int]:
        # Good technique to remove the invalids by using the prefix sum till n than extra invalids need to remove also from using maths
        n = len(s)
        
        # Note: Instead dealing with n we are dealing with n+1 i.e 1 index array    
        pre0 = [0] * (n + 1)
        pre1 = [0] * (n + 1)
        
        for i in range(n):
            pre0[i + 1] = pre0[i] + (s[i] == '0')
            pre1[i + 1] = pre1[i] + (s[i] == '1')
        
        rightMax = [0]  # n + 1 elements find valid index to the right i.e [i,rightMax[i]) will binary stringify
        for i in range(n):
            j0 = bisect_left(pre0, k + 1 + pre0[i]) # already have pre0[i] at i need more k+1
            j1 = bisect_left(pre1, k + 1 + pre1[i]) # already have pre1[i] at i need more k+1
            idx = max(j0, j1)
            rightMax.append(idx)  # shift by 1 so <= n

        # Compute the prefix sum from the end bcz if we add the elements after high till n one by one to the subarray then all those will be invalids subarrays rememenber taking those till n
        endSum = [0] * (n + 1)
        for i in range(1, n + 1):
            endSum[i] = endSum[i-1] + ((n+1 - rightMax[i]) if rightMax[i] <=n else 0)  # [rightMax[i], n+1)

        res = []
        for l, r in queries:
            l += 1  # make 1 index both
            r += 1  # make 1 index both
            # find the rightMax index between l to r which are less than equal r
            # below those will have contribution in invalids
            high = bisect_right(rightMax, r, lo=l, hi=r) - 1
            
            lnt = r-l+1
            curr = lnt * (lnt+1) // 2  # subarray count n * (n+1) // 2
            if high < 0:  # whole subarray is valid
                result.append(curr)
                continue
            
            # indices between [l, high] have contribution in invalids by extending l to high indices
            invalids = endSum[high] - endSum[l-1]
            # extra invalids count as we are extending till the n so remove thoses
            # i.e  [l, high] extends extra (r, n+1) or say (r, n]
            invalids -= (high - l + 1) * (n - r)
            res.append(curr - invalids)

        return res

        
        
        
            
74600