<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]:
        n = len(s)
        # rightMostInd stores the rightmost ind meaning at every ind what is the rightmost uptil which the substring starting from this ind is valid. This helps us since we are given queries and we dont know uptil what index we will find a valid substring upto. For eg. in eg1 we are given a query [0,6] but if we find the rightMostInd arr we will see that at ind 0 the right most ind uptil which we will find a valid substring is ind 4. So we can say that the number of substrings valid at ind 0 will be 5*(5+1)//2 
        rightMostInd = [0]*n
        i = j = n-1
        cnt_0 = 0
        cnt_1 = 0
        while j>=0:
            if s[j] == "0":
                cnt_0+=1
            else:
                cnt_1+=1
            while i>j and cnt_1>k and cnt_0>k:
                if s[i] == "0":
                    cnt_0-=1
                else:
                    cnt_1-=1
                i-=1
            rightMostInd[j] = i
            j-=1
        
        # for index j what is the left most index i uptil we can get a valid substring
        leftMostInd = [0]*n
        
        i = j = 0
        cnt_0 = cnt_1 = 0
        while j<n:
            if s[j] == "0":
                cnt_0+=1
            else:
                cnt_1+=1
            while i<=j and cnt_1>k and cnt_0>k:
                if s[i] == "0":
                    cnt_0-=1
                else:
                    cnt_1-=1
                i+=1
            leftMostInd[j] = i
            j+=1
        prefixSum = [0]*n
        prefixSum[0] = 1
        for i in range(1,n):
            prefixSum[i] = prefixSum[i-1]+(i-leftMostInd[i]+1)
        res = 0
        ans = []
        # print(rightMostInd)
        for q1,q2 in queries:
            low = q1
            high = q2
            rightValidInd = min(q2,rightMostInd[q1])
            length = rightValidInd-low+1
            res = (length*(length+1))//2 #Total Substrings
            if rightValidInd < q2:
                res+=prefixSum[q2]-prefixSum[rightValidInd]
            ans.append(res)
        return ans

        
73200