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

class Solution:
    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        ## RC ##
        ## APPROACH: BIT MANIPULATION, BIT MASK, XOR ##
        ## As per question 'We may rearrange the substring s[lefti...righti] for each query then choose up to ki'
        ## ^ this indicates that substring order doesn't matter, only frequency of characters is needed to check if it is palindrome
        ## LOGIC ##
        ## Maintain alphabets counter at each index, just like prefix_sum ( but for all alphabets )
        ## Given a range [i,j], use these prefix alphabet counters of (i-1 and j) to figure out palindrome or not 

        ## Wait, do we really need alphabet counters ?
        ## Can {a:2, b:1, c:1} be {a: 0, b:1, c:1} ? Making it binary, so that bit mask operations can be used.
        ## How can we do prefix_sum ? adding counters from previous element ? just XOR should do.

        ## How can we substract prefix_sum[j] - prefix_sum[i-1] ? even for this XOR should do.
        ## Example: abcdae --> query [2,5]
        ## prefix_mask[5] = '01111' # 'abcdae'
        ## prefix_mask[1] = '11000' # 'ab'
        ## result should  = '10111' # 'cdae' ==> can be obtained from XOR

        ## Play around with << operator and ^ xor operator
        ## 1 << idx_of_char --> mask value ==> will give binary value but when printed here in decimal it might look different
        ## Example: a = 1<<0 ==> 1 (binary) --> 1(decimal)
        ## Example: c = 1<<2 ==> 100 (binary) --> 8(decimal)
        ## Example: x = 1<<23 ==> 1000000... (binary) --> 8388608(decimal)
        n = len(s)
        prefix_counter = [0] * (n+1)    # for i-1, when i=0, we want 0, so appending one element extra
        prefix_counter[0] = 1<<(ord(s[0])-ord('a'))
        for i in range(1, n):
            prefix_counter[i] = ( prefix_counter[i-1] ) ^ ( 1<<(ord(s[i])-ord('a')) )
        # print(prefix_counter)

        res = []
        for q in queries:
            mask = prefix_counter[q[1]] ^ prefix_counter[q[0]-1]
            # print(mask, bin(mask))
            res.append( mask.bit_count()//2 <= q[2] )
        return res

980