<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)
            s = ['~']+list(s)

            cum0 = [0] * (n + 1)
            cum1 = [0] * (n + 1)
            cums= [0] * (n + 1)
            leftmost={}
            rightmost={}
            l=1
            for r in range(1,n+1):
                cum0[r] = cum0[r-1] + (1 if s[r] == '0' else 0)
                cum1[r] = cum1[r-1] + (1 if s[r] == '1' else 0)
                while cum0[r] - cum0[l-1] > k and cum1[r]-cum1[l-1] > k:
                    leftmost[l] = r-1
                    l+=1
                cur = r - l + 1
                cums[r] = cums[r-1] + cur
                rightmost[r] = l
                leftmost[l] = r
            for i in range(l+1,n+1):
                leftmost[i] = n
            # print('s', s)
            # print('leftmost', leftmost)
            # print('rightmost', rightmost)
            # print('cums', cums)

            ans = []

            def cal(i):
                return (i*(i+1))//2

            for li, ri in queries:
                li+=1; ri+=1
                ra=leftmost[li]
                if ra>=ri:
                    ans.append(cal(ri-li+1))
                    continue

                lcnt=(cal(ra - li+1))

                mcnt = cums[ri] - cums[ra]

                lb = rightmost[ri]
                rcnt= 0#cal(ri-lb)
                # print('s',s)
                # print(f'li={li}, ri={ri}, (li={li},ra={ra}), (lb={lb}, ri={ri})')
                # print(f'lcnt={lcnt}, mcnt={mcnt}, rcnt={rcnt}')

                ans.append(lcnt+mcnt+rcnt)

            return ans
79200