<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)
        
#         dp_r = [0] * n
#         l = 0
#         cnt = defaultdict(int)
#         for r in range(n):
#             cnt[s[r]] += 1
#             while cnt["0"] > k and cnt["1"] > k:
#                 cnt[s[l]] -= 1
#                 l += 1
#             dp_r[r] = dp_r[r - 1] + (r - l + 1)
        
#         l2r = [0] * n
#         r = n - 1
#         cnt = defaultdict(int)
#         for l in range(n - 1, -1, -1):
#             cnt[s[l]] += 1
#             while cnt["0"] > k and cnt["1"] > k:
#                 cnt[s[r]] -= 1
#                 r -= 1
#             l2r[l] = r
#         print(dp_r)
#         print(l2r)
#         ans = [0] * len(queries)
#         for i, (l, r) in enumerate(queries):
#             m = min(r, l2r[l])
#             w = m - l + 1
#             cnt = (w) * (w + 1) // 2
#             if r > m:
#                 cnt += dp_r[r] - dp_r[m]
#             ans[i] = cnt
        
#         return ans


class Solution:
    def countKConstraintSubstrings(self, s: str, k: int, queries: List[List[int]]) -> List[int]:
        n = len(s)
        
        a = [0] * n
        pref_sum=[0]*(n+1)
        l = 0
        cnt = defaultdict(int)
        for r in range(n):
            cnt[s[r]] += 1
            while cnt["0"] > k and cnt["1"] > k:
                cnt[s[l]] -= 1
                l += 1
            a[r] = r - l + 1

        for i in range(n):
            pref_sum[i+1]=pref_sum[i]+a[i]

        
        
        l2r = [0] * n
        r = n - 1
        cnt = defaultdict(int)
        for l in range(n - 1, -1, -1):
            cnt[s[l]] += 1
            while cnt["0"] > k and cnt["1"] > k:
                cnt[s[r]] -= 1
                r -= 1
            l2r[l] = r
        
        ans = [0] * len(queries)
        for i, (l, r) in enumerate(queries):
            m = min(r, l2r[l])
            w = m - l + 1
            cnt = (w) * (w + 1) // 2
            if r > m:
                cnt += pref_sum[r+1] - pref_sum[m+1]
            ans[i] = cnt
        
        return ans
73400