问题描述
给你一个字符串 s，请你对 s 的子串进行检测。
每次检测，待检子串都可以表示为 queries[i] = [left, right, k]。我们可以 重新排列 子串 s[left], ..., s[right]，并从中选择 最多 k 项替换成任何小写英文字母。
如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为 true，否则结果为 false。
返回答案数组 answer[]，其中 answer[i] 是第 i 个待检子串 queries[i] 的检测结果。
示例
输入：s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
输出：[true,false,false,true,true]
解释：
queries[0] : 子串 = "d"，回文。
queries[1] : 子串 = "bc"，不是回文。
queries[2] : 子串 = "abcd"，只替换 1 个字符是变不成回文串的。
queries[3] : 子串 = "abcd"，可以变成回文的 "abba"。 也可以变成 "baab"，先重新排序变成 "bacd"，然后把 "cd" 替换为 "ab"。
queries[4] : 子串 = "abcda"，可以变成回文的 "abcba"。
解题思路
核心思路：前缀和+异或运算
- 首先，理解题目内容：截取字符串
s中部分连续的字符，可以对字符进行重新排列，并替换k个字符，是否可以构成回文字符串； - 要检测是不是回文字符串，我们就得知道当前截取到的字符串的组成（字母的种类及个数）；那么，自然而然的可以想到使用前缀和的方式：我们可以遍历原字符串
s，并记录在头开始到每个字符位置的字符串的字母状态（字母的种类及个数）；用后一个字母状态减去前一个字母状态，就可以得到截取部分的字母状态了； - 得到了字母的组成，那么如何判断回文字符串呢？
我们要对每种字母进行分析，如果字母的个数是偶数，那么在构成回文字符串的时候，我们完全可以将这些字母均匀的放在回文字符串的两边；也就是说，偶数个的字母，我们可以直接忽略对回文串的影响；
如果字母的个数是奇数，那么就要进行具体的分析：
如果奇数个的字母只有1个，仍然可以构成回文串；
如果奇数个的字母只有2个，需要修改1个字母才能构成回文串；
如果奇数个的字母只有3个，仍然是需要修改1个字母才能构成回文串；
也就是说，如果奇数个的字母为n个，需要修改2/n个字母才能构成回文串。 - 优化：异或运算
在上述的步骤中，我们统计了字母的种类及其个数；其实，我们并不需要知道具体的数量，需要知道的是字母个数的奇偶变化；如果奇变奇、偶变偶，那么可能没有变化，也有可能多了偶数个，对回文串的构成没有影响；如果是奇偶互变，那么肯定是发生了奇数个的变化，统计变化的数量即可。
另外，我们现在使用一个长为26位的数组来存放了字母的个数，我们可以对此进行优化：将数组压缩为一个二进制数进行存放。
那么在遍历字符串s，如何修改某个字母的个数状态（现在只存奇偶）呢？
修改a出现的数量时，与二进制数1进行异或；
修改b出现的数量时，与二进制数10进行异或；
修改c出现的数量时，与二进制数100进行异或；
修改d出现的数量时，与二进制数1000进行异或；
以此类推...
代码示例（JAVA）
初步代码，使用前缀和
class Solution {
public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
int len = s.length();
int[][] arr = new int[len + 1][26];
// 统计前缀和
for (int i = 0; i < len; i++) {
char c = s.charAt(i);
arr[i + 1] = arr[i].clone();
arr[i + 1][c - 'a']++;
}
List<Boolean> res = new ArrayList<>();
for (int[] query : queries) {
int left = query[0], right = query[1], k = query[2];
// 统计奇数的数量
int count = 0;
for (int i = 0; i < 26; i++) {
if ((arr[right + 1][i] - arr[left][i]) % 2 != 0) {
count++;
}
}
// 添加结果
res.add(count / 2 <= k);
}
return res;
}
}
优化：前缀和+异或运算
class Solution {
public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
int len = s.length();
int[] arr = new int[len + 1];
// 统计前缀和
for (int i = 0; i < len; i++) {
int b = 1 << (s.charAt(i) - 'a');
arr[i + 1] = arr[i] ^ b;
}
List<Boolean> res = new ArrayList<>();
for (int[] query : queries) {
int left = query[0], right = query[1], k = query[2];
// 统计奇数的数量
int count = Integer.bitCount(arr[right + 1] ^ arr[left]);
// 添加结果
res.add(count / 2 <= k);
}
return res;
}
}
