<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>

from typing import List

debug_show_map = True 
debug_show_matches_from_right = True

def get_right_match_map(s: str, k: int) -> Dict[int, int]:
    match_map = dict()
    n = len(s)
    count = [0,0]
    start, end = 0,0
    count[int(s[0])] += 1 
    while start < n:
        #print(f"start, end, count, {start, end, count}")
        if count[0] >= k+1 and count[1] >= k+1:
            match_map[start] = end - 1
            start += 1
            count[int(s[start-1])] -= 1
            continue
        if end == n-1:
            match_map[start] = end
            count[int(s[start])] -= 1
            start += 1
            continue
        
        end += 1
        count[int(s[end])] += 1
        

    return match_map

def substring_counts(n: int) -> int:
    return n + (n*(n-1)) // 2

def left_match(match_map: Dict[int, int], size:int) -> List[int]:
    matches = [-1] * size
    for indx,match in match_map.items():
        matches[match] = max(matches[match], indx)

    zero_match = match_map[0]
    #matches[0] = 0
    for i in range(zero_match, size):
        if matches[i] != -1:
            continue
        matches[i] = matches[i-1]

    if debug_show_matches_from_right:
        print(f"matches from right {matches}")
    return matches



class Solution:
    def countKConstraintSubstrings(self, s: str, k: int, queries: List[List[int]]) -> List[int]:
        n = len(s)
        if n == 1:
            return [1]

        right_match_map = get_right_match_map(s, k) # this indx is the last right indx for a good substring.
        if debug_show_map:
            print(f"right_match_map is {right_match_map}")


        counts = [0] * (n+1)
        for i in range(n):
            counts[i+1] = counts[i] + right_match_map[i] - i + 1    
        to_return = []

        left_matches = left_match(right_match_map, len(s))
        for quer in queries:
            left,right = quer
            cut_off_right = right_match_map[left]
            if right <= cut_off_right:
                ans = substring_counts(right-left+1)
                to_return.append(ans)
                continue

            last_indx_before_over_shooting  = left_matches[right]
            if last_indx_before_over_shooting == -1:
                return substring_counts(right - left + 1)
            partials = counts[(last_indx_before_over_shooting) + 1] - counts[(left+1) - 1]
            left_over = substring_counts(right - (last_indx_before_over_shooting + 1) + 1)

            ans = partials + left_over
            to_return.append(ans)

        return to_return
80400