摘要：本题需要充分挖掘回文的性质，重点理解「重新排列」这个题目中的关键字，并且充分理解「异或」运算的特点。

题解 |「力扣」第 1177 题：构建回文串检测

给你一个字符串 s，请你对 s 的子串进行检测。

每次检测，待检子串都可以表示为 queries[i] = [left, right, k]。我们可以 重新排列 子串 s[left], ..., s[right]，并从中选择最多 k 项替换成任何小写英文字母。

如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为 true，否则结果为 false。

返回答案数组 answer[]，其中 answer[i] 是第 i 个待检子串 queries[i] 的检测结果。

注意：在替换时，子串中的每个字母都必须作为 独立的 项进行计数，也就是说，如果 s[left..right] = "aaa" 且 k = 2，我们只能替换其中的两个字母。（另外，任何检测都不会修改原始字符串 s，可以认为每次检测都是独立的）。

示例：

输入：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"。
复制代码

提示：

$1 \le s.length, queries.length \le 10^5$
$0 \le queries[i][0] \le queries[i][1] < s.length$
$0 \le queries[i][2] \le s.length$
s 中只有小写英文字母

知识点：

异或前缀和的和组成了区间里的信息；
本题还利用的「状态压缩」的技巧。

思路分析：

替换最多 k 次以后还可以调整小写英文字母的位置，组成回文；
暴力解法是枚举所有子串 s[i..j] 中 26 个小写英文字母出现的次数；
重点理解「重新排列」这个词，怎么排列其实题目并不关心，因此我们只需要关心 每一个 query 的字符出现的次数；
而 query 表示的是字符串的连续子区间，因此我们需要掌握字符串的子区间里字符出现的次数；
重点：回文性质中，如果一个字符出现偶数次，可以把它们放在字符串对称的位置，出现偶数次的字符串我们可以不关心。换句话说，k 次使用机会应该先满足出现次数为奇数的字符串，并且只应该替换单独的，不可以组成配对的字符；
要掌握连续子区间里的信息，容易想到使用前缀和。

参考代码：

import java.util.ArrayList;
import java.util.List;

public class Solution {

    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        int len = s.length();
        char[] charArray = s.toCharArray();

        // 第 1 步：计算前缀异或和
        int[] preSum = new int[len + 1];
        preSum[0] = 0;
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] ^ (1 << (charArray[i] - 'a'));
        }
        // 第 2 步：根据前缀异或和计算结果
        List<Boolean> res = new ArrayList<>();
        for (int[] query : queries) {
            // 注意理解这里计算区间和的异或相减关系
            res.add(Integer.bitCount(preSum[query[0]] ^ preSum[query[1] + 1]) / 2 <= query[2]);
        }
        return res;
    }
}
复制代码

说明：

preSum[query[0]] ^ preSum[query[1] + 1]
复制代码

异或前缀和，求的就是区间和，这是因为「异或」运算的特点是：不进位的加法。相同的数位进行异或以后，得到的数位是 $0$ 。

关联问题：

191. 位1的个数

参考代码：

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0) {
            n &= n - 1;
            res++;
        }
        return res;
    }
}
复制代码