<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 {
// public:
//     bool check(string s, int k){
//         int n=s.size();
//         unordered_map<char,int>mp;
//         for(int i=0;i<n;i++){
//             mp[s[i]]++;
//         }
//         int count=0,c=0;
//         for(auto it:mp){
//            // if(it.second%2==0)count++;
//             if(it.second%2!=0)c++;
//         }
//         // int a=count*2;
//         // int b=n-a-c;
//         int b;
//         b=c/2;
//         if(k>=b)return true;
//         else return false;
        
//     }
//     vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
//         int n=s.size();
//         int m=queries.size();
//         vector<bool>ans;
//         for(int i=0;i<m;i++){
//             string str=s.substr(queries[i][0],queries[i][1]-queries[i][0]+1);
//             if(check(str,queries[i][2])){
//                 ans.push_back(true);
//             }else ans.push_back(false);
//         }
//         return ans;
//     }
// };
class Solution {
public:
    vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
        
        int n = s.size();
        
        unordered_map<int,vector<int>> mp;
        vector<int> freq(26,0);
        mp[-1] = freq;
        
        for(int i = 0; i<n; i++){
            freq[s[i]-97]++;
            mp[i] = freq;
        }
        
        int m = queries.size();
        vector<bool> ans(m);
        
        for(int i = 0; i<m; i++){
            int l = queries[i][0];
            int r = queries[i][1];
            int k = queries[i][2];
            
            vector<int> freq(26,0);
            int odd_cnt = 0;
            
            for(int j = 0; j<26; j++){
                freq[j] = mp[r][j] - mp[l-1][j];
                if(freq[j]&1)
                    odd_cnt++;
            }
            
            
            
            if(odd_cnt/2 > k){
                ans[i] = false;
            }
            else{
                ans[i] = true;
            }
            
            
        }
        
        return ans;
        
    }
};
197439