每日一题：构建回文串检测

给你一个字符串 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 ，可以认为每次检测都是独立的）

题目链接：https://leetcode.cn/problems/can-make-palindrome-from-substring/

# 解题思路

只须统计每个子字符串中各个字符的个数，且只须关心个数为奇数的字符的数量即可。要想使用最少的变换次数让子字符串变成回文串，则只需要将奇数个的字符进行处理，即取一半即可。

前缀和 + 位运算：

1. 因为只含小写字母，所以可以用一个 int 整数来便是当前字符是哪一个，譬如：
   a -> 1<<0 ， b -> 1<<1 ，...， z -> 1<<25 。
2. ps[i] 表示 s 中 [0, i) 范围上只有奇数个字母的数量，用数位 1 表示当前字母的个数为奇数个。那么对于 s 上的任意范围 [i, j] 上【个数为奇数的字母】的数量就等于 ps[j+1] ^ ps[i] 中【数位 1】的数量。
3. 也就是说，k 只要大于或等于【需要的最少次数】就能把当前子字符串变成回文串。

# 代码

class Solution {

    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {

        int n = s.length();

        // 统计每个小写字母异或前缀和

        // 奇数 -> 1

        // 偶数 -> 0

        // 刚好用来表示奇偶性，最后统计奇数有多少个，即统计整数的 bit 中有多少个 1

        int[] ps = new int[n + 1];

        for (int i = 0; i < n; ++i) {

            ps[i + 1] = ps[i] ^ (1 << (s.charAt(i) - 'a'));

        }

        List<Boolean> ans = new ArrayList<>();

        for (int[] q : queries) {

            int oddCnt = Integer.bitCount(ps[q[1] + 1] ^ ps[q[0]]);

            // 只需统计数量为奇数的字母种类数即可，

            // 最小需要替换的字母数就是 oddCnt / 2（整除）

            ans.add(q[2] >= (oddCnt >> 1));

        }

        return ans;

    }

}