题目链接：1177. 构建回文串检测
方法：状态压缩 + 前缀异或
解题思路
- 由题可知对于询问 \(queries[i] = [l, r, k]\)，\([l, r]\) 子串可以重新排列，那么此时子串只要满足最终子串中至多有一个字母的数量为奇数（此时其排在中心，其他字母均分在两侧）；
- 那么就需要知道，在 \([l, r]\) 区间中各字母数量的奇偶性，这可以通过前缀异或来快速获得；
- 首先将字母映射到一个 \(26\) 位的二进制数（实际以十进制表示）上，
'a' => 第0位，这样就可以将字符串中的每个字母转化为一个二进制数； - 然后初始化前缀异或数组 \(cnt\)，\(cnt[i + 1]\) 表示字符串前 \(i\) 个字母对应的二进制数的异或值；
- 这样就可以计算出 \([l, r]\) 区间的异或值，\(cnt[r + 1]\) ^ \(cnt[l]\)，其中某一位为 1 表示其对应的字母为奇数，当区间内奇数的字母数量 \(bits <= 2 * k + 1\) 时，就可以转换为回文串，因为每替换一个可以取出一对奇数的情况，最后允许只有一个字母数量为奇数。
代码
class Solution {
public:
vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
int n = s.length();
vector<int> cnt(n + 1);
for (int i = 0; i < n; i ++ ) {
cnt[i + 1] = cnt[i] ^ (1 << (s[i] - 'a'));
}
vector<bool> ans;
for (auto &q : queries) {
int l = q[0], r = q[1], k = q[2];
int bits = 0, x = cnt[r + 1] ^ cnt[l];
while (x) {
int c = x & -x;
x -= c;
bits ++ ;
}
ans.push_back(bits <= 2 * k + 1);
}
return ans;
}
};
复杂度分析
时间复杂度：初始化前缀异或数组 — \(O(n)\)，每次查询 — \(O(1)\)；
空间复杂度：\(O(n)\)。