1177. Can Make Palindrome from Substring

Given a string s, we make queries on substrings of s.

For each query queries[i] = [left, right, k], we may rearrange the substring s[left], …, s[right], and then choose up to k 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 an array answer[], where answer[i] is the result of the i-th query queries[i].

Note that: Each letter is counted individually for replacement so if for example s[left..right] = “aaa”, and k = 2, we can only replace two of the letters. (Also, note that the initial string s is never modified by any query.)

class Solution {
public:
    vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
        int mask = 0;
        vector<int> masks(1);
        vector<bool> res(queries.size());

        for(char& c : s) {
            masks.push_back(mask ^= 1 << (c - 'a'));
        }

        for(int i = 0 ; i < queries.size(); i++) {
            res[i] = queries[i][2] >= __builtin_popcount(masks[queries[i][1] + 1] ^ masks[queries[i][0]]) >> 1;
        }

        return res;
    }
};