題目鏈接：https://leetcode.cn/problems/can-make-palindrome-from-substring/description/

題目大意：給出一個字符串s，每次query給出l, r, k，要求判斷子串s[l:r+1]在經過k次操作后是否能變為回文串。一次操作可以將子串內的一個字符變為任意一個其他字符。并且子串順序可以任意改變。

思路：因為有很多query，自然想到會有重復計算，要檢查超時，那么就想到前綴和。用pre[j][i]記錄到i為止字母j出現的次數。那么子串內字母j出現的次數即為pre[j][r+1-l]。

對于子串，如果長度為奇數，那么回文與否與中間的字符無關，我們可以忽略。因此處理的總是一個總長度為偶數的子串。統計子串中每個字母的出現次數，可以知道，【奇數出現的次數】必然是偶數，因為只有偶數個奇數+若干偶數才能使得和（子串總長度）為偶數。

那么對于cnt個出現奇數次的字母，我們進行k次操作可以最多讓2*k長度的子串變為回文。而對于出現偶數次的字母，只需將其對稱排列即可。因此判斷條件變為cnt / 2 <= k

完整代碼

class Solution {
public:vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {int N = s.length();int pre[26][10001] = {};for (int i = 0; i < N; i++) {int idx = s[i]-'a';pre[idx][i+1] = pre[idx][i]+1;for (int j = 0; j < 26; j++) {if (j != idx && i > 0)pre[j][i+1] = pre[j][i];}}vector<bool> res;for (auto q: queries) {int l = q[0], r = q[1], k = q[2];char mid = s[(l+r)/2];bool flag = (r+1-l)%2;int arr[26] = {};if (flag)arr[mid-'a']--;int cnt = 0;for (int j = 0; j < 26; j++) {arr[j] += pre[j][r+1] - pre[j][l];if (arr[j] & 1 == 1) {cnt++;}}if (cnt / 2 <= k) {res.emplace_back(true);}else {res.emplace_back(false);}}return res;}
};

然而，碰到大的測試樣例的時候會超時…那么就不得不求助高效的位運算了。

我們用一個二進制數組存儲前綴和，每個二進制數一共26位，代表某個字母在i位置前的奇偶性。奇偶性運算用異或操作^來實現。

        int N = s.length();vector<int> pre(N+1, 0);for (int i = 0; i < N; i++) {pre[i+1] = pre[i] ^ (1 << s[i]-'a');            }

如何統計子串中的字母的奇數的個數呢？這就是數一下【代表該區間的二進制數】（通過前綴和做差得到）中1的個數。

            int l = q[0], r = q[1], k = q[2];int cnt = 0;int x = pre[r+1] ^ pre[l];while (x > 0) {x &= x - 1;cnt++;}

x &= x-1操作將 x 的二進制表示中最低位的 1 翻轉成 0，并將所有更低位的位都清零。這是一個位運算技巧，快速計算二進制數中1的個數。

另外，由于乘法比除法更加快速，我們就不考慮是否忽略子串最中間的字母了，即使它使得x中1的個數增加了，也只不過增加1而已，我們將能夠處理的上限改為2*k+1即可。

            if (cnt <= 2*k+1)res.emplace_back(true);elseres.emplace_back(false);

完整代碼

class Solution {
public:vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {int N = s.length();vector<int> pre(N+1, 0);for (int i = 0; i < N; i++) {pre[i+1] = pre[i] ^ (1 << s[i]-'a');            }vector<bool> res;for (auto q: queries) {int l = q[0], r = q[1], k = q[2];int cnt = 0;int x = pre[r+1] ^ pre[l];while (x > 0) {x &= x - 1;cnt++;}if (cnt <= 2*k+1)res.emplace_back(true);elseres.emplace_back(false);}return res;}
};