You are given a string s and array queries where queries[i] = [lefti, righti, ki]. We may rearrange the substring s[lefti...righti] for each query and then choose up to ki of them to replace with any lowercase English letter.

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

Return a boolean array answer where answer[i] is the result of the ith query queries[i].

Note that each letter is counted individually for replacement, so if, for example s[lefti...righti] = "aaa", and ki = 2, we can only replace two of the letters. Also, note that no query modifies the initial string s.

&nbsp;
Example :

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


Example 2:

Input: s = "lyb", queries = [[0,1,0],[2,2,1]]
Output: [false,true]


&nbsp;
Constraints:


	1 &lt;= s.length, queries.length &lt;= 105
	0 &lt;= lefti &lt;= righti &lt; s.length
	0 &lt;= ki &lt;= s.length
	s consists of lowercase English letters.


class Solution:
    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        hash_map = {s[0]: 1}
        x = hash_map
        prefix = [hash_map]
        for i in range(1, len(s)):
            x = x.copy()
            x[s[i]] = x.get(s[i], 0) + 1
            prefix.append(x)
            
        result = []
        for query in queries:
            cnt = 0
            for key, value in prefix[query[1]].items():
                if query[0] > 0:
                    x = value - prefix[query[0]-1].get(key, 0)
                else:
                    x = value
                if x % 2:
                    cnt+=1
            if cnt - 2 * query[2] > 1:
                result.append(False)
            else:
                result.append(True)
        return result
class Solution 
{
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) 
    {
        List<Boolean> list = new ArrayList<>();
        
        int n = s.length();
        int[][] map = new int[n+1][26];
        
        for(int i=0;i<s.length();i++)
        {
            for(int j=0;j<26;j++)
                map[i+1][j] = map[i][j];
            
            map[i+1][s.charAt(i) - 'a']++;
        }
        
        for(int[] q : queries)
        {
            int l = q[0];
            int r = q[1];
            int k = q[2];
            int count = 0;
            
            for(int i=0;i<26;i++)
                count += (map[r+1][i] - map[l][i]) % 2;
            
            list.add(count/2 <= k);
        }
        
        return list;
    }
}
class Solution {
public:
  vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
    vector<vector<int>>table(s.size(), vector<int>(26,0));
    vector<bool>ans;

    table[0][s[0]-'a']++;
    for(int i = 1; i != s.size(); i++){
      for(int j = 0; j != 26; j++) table[i][j] = table[i-1][j];
      table[i][s[i]-'a']++;
    }

    for(auto &q: queries){
      int odd = 2 + (q[2]<<1);
      for(int i = 0; i != 26; i++){
        int val = table[q[1]][i] - (q[0] ? table[q[0]-1][i] : 0);
        if( (val & 1) && --odd == 0){ans.push_back(false); goto mark;}
      }

      ans.push_back(true);
      mark:;
    }

    return ans;
  }
};
const getBitCount = (n) => {
    let cnt = 0;
    while(n > 0) {
        cnt += n & 1;
        n >>= 1;
    }
    return cnt;
}

var canMakePaliQueries = function(s, queries) {
    const masks = [0], base = 'a'.charCodeAt(0);
    let mask = 0;
    for(let c of s) {
        mask ^= (1 << (c.charCodeAt(0) - base));
        masks.push(mask);
    }
    return queries.map(([l, r, k]) => {
        const cnt = getBitCount(masks[l] ^ masks[r+1]);
        return cnt - 1 <= 2 * k
    });
};
Can Make Palindrome from Substring