2023.6.16 构建回文串检测

注意关键性质，可以重排。所以我们可以只考虑一种情况，其他情况都可以重排到这种情况。
考虑在区间内：

1. 所有字符都有偶数个，此时不需要改变任何字符，我们可以把字符重排成回文的。
2. 只有一种字符有奇数个，其他字符都是偶数个。此时可以拿出这种字符的一个放在最中间。然后又回归到情况1，可以重排成回文。
3. 有两种字符有奇数个，其他字符偶数个。此时可以把其中一种字符的一个变成另外一种，回归情况1。（变化了一次）
4. 有三种字符有奇数个，其他字符偶数个。此时可以把其中一种字符的一个变成另外一种，回归情况2。（变化了一次）
5. 有四种字符有奇数个，其他字符偶数个。此时可以把其中一种字符的一个变成另外一种，再把剩下的两种也进行一次这种操作，回归到情况1。（变化了二次）
   ...

以此类推，可以看出，变化的次数是奇数字符的个数除以2。统计一个范围内字符的奇偶，可以用前缀和，由于只看奇偶，使用异或前缀和可以进一步压缩空间。

impl Solution {
    pub fn can_make_pali_queries(s: String, queries: Vec<Vec<i32>>) -> Vec<bool> 
    {
        let n = s.len();
        let mut prefix = vec![0; n + 1];

        for (i, c) in s.chars().enumerate() {
            let idx = c as u8 - 'a' as u8;
            prefix[i + 1] = prefix[i] ^ (1 << idx);
        }

        let mut res = Vec::new();
        for query in queries {
            let (l, r, k) = (query[0], query[1], query[2]);
            let cnt = ((prefix[(r + 1) as usize] ^ prefix[l as usize]) as usize).count_ones(); // 计算出奇数字符的个数
            res.push(cnt / 2 <= (k as u32));
        }
        res
    }
}