<p>You are given a string <code>s</code> and array <code>queries</code> where <code>queries[i] = [left<sub>i</sub>, right<sub>i</sub>, k<sub>i</sub>]</code>. We may rearrange the substring <code>s[left<sub>i</sub>...right<sub>i</sub>]</code> for each query and then choose up to <code>k<sub>i</sub></code> of them to replace with any lowercase English letter.</p>

<p>If the substring is possible to be a palindrome string after the operations above, the result of the query is <code>true</code>. Otherwise, the result is <code>false</code>.</p>

<p>Return a boolean array <code>answer</code> where <code>answer[i]</code> is the result of the <code>i<sup>th</sup></code> query <code>queries[i]</code>.</p>

<p>Note that each letter is counted individually for replacement, so if, for example <code>s[left<sub>i</sub>...right<sub>i</sub>] = &quot;aaa&quot;</code>, and <code>k<sub>i</sub> = 2</code>, we can only replace two of the letters. Also, note that no query modifies the initial string <code>s</code>.</p>

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

<pre>
<strong>Input:</strong> s = &quot;abcda&quot;, queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
<strong>Output:</strong> [true,false,false,true,true]
<strong>Explanation:</strong>
queries[0]: substring = &quot;d&quot;, is palidrome.
queries[1]: substring = &quot;bc&quot;, is not palidrome.
queries[2]: substring = &quot;abcd&quot;, is not palidrome after replacing only 1 character.
queries[3]: substring = &quot;abcd&quot;, could be changed to &quot;abba&quot; which is palidrome. Also this can be changed to &quot;baab&quot; first rearrange it &quot;bacd&quot; then replace &quot;cd&quot; with &quot;ab&quot;.
queries[4]: substring = &quot;abcda&quot;, could be changed to &quot;abcba&quot; which is palidrome.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;lyb&quot;, queries = [[0,1,0],[2,2,1]]
<strong>Output:</strong> [false,true]
</pre>

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

<ul>
	<li><code>1 &lt;= s.length, queries.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= left<sub>i</sub> &lt;= right<sub>i</sub> &lt; s.length</code></li>
	<li><code>0 &lt;= k<sub>i</sub> &lt;= s.length</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

import string

class Solution:
    def can_be_palindrome(self, curr_freqs, k):
        odds_to_remove = 0
        # for i in Counter(s).values():
        for i in curr_freqs.values():
            if i % 2 == 1:
                odds_to_remove += 1
        
        if odds_to_remove <= 1: return True

        # 1 odd is allowed
        odds_to_remove -= 1

        # if we can make odds_to_remove 0, we can make palindrome
        return odds_to_remove <= k * 2


    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        res = []

        prefix_sums = [{i: int(s[0] == i) for i in string.ascii_lowercase}]

        for char in s[1:]:
            new_item = prefix_sums[-1].copy()
            new_item[char] += 1
            prefix_sums.append(new_item)

        for start, end, k in queries:
            # TLE - because we do Counter for 10^5 times, so calculate frequencies dynamically
            # using prefix sums
            # res.append(
            #     self.can_be_palindrome(s[start: end + 1], k),
            # )

            curr_freqs = prefix_sums[end].copy()
            curr_freqs[s[start]] += 1

            for char, freq in prefix_sums[start].items():
                curr_freqs[char] -= freq

            res.append(
                self.can_be_palindrome(curr_freqs, k),
            )

        return res

1639