Loading... 这道题有一个关键条件就是 l..r 之间的字符可以重排，那么我们只需要关注字符频次满足回文串要求即可。 - 长度为偶数的情况下，需要满足所有的字符频次为偶数。 - 长度为奇数的情况下，有一个字符是奇数频次。 而字符频次可以巧妙的转换成用异或进行统计，因为只有奇数频次才会是1。 然后因为我们是需要多次查询，所以可以提前进行预处理，像这种涉及区间查询的问题，常用的手段就是前缀和，这道题也不例外。 构造一个 prefix 长度为 n+1，那么 $prefix[i+1] = prefix[i] \oplus (1 << (s[i] - 'a'))$ 那么任意区间 [l, r] 的奇数频次的字符个数就是 $prefix[r+1] \oplus prefix[l]$ 当然，这里还需要统计二进制 1 的个数才是字符个数，因为用了二进制压缩的手法进行保存。 那么剩下的就简单了，奇数频次的字符个数 / 2 <= k 就能保证构造出回文串了。 具体的我们可以看看刚才所述条件，那就是奇数频次的字符个数需要小于等于 1，这不仅代表着回文串的构造条件，同时也代表了字符串长度的奇偶性。 一次变换最多能够将两个字符的奇数频次修改掉，举个例子 abc，如果我们把 c 变成 a，就相当于两个字符变成了偶数频次了。 所以最终得到代码实现如下： ```go func canMakePaliQueries(s string, queries [][]int) []bool { n := len(s) prefix := make([]int, n+1) for i, c := range s { prefix[i+1] = prefix[i] ^ (1 << (c - 'a')) } res := make([]bool, len(queries)) for i, q := range queries { l, r, k := q[0], q[1], q[2] xor := prefix[r+1] ^ prefix[l] oddCnt := bits.OnesCount(uint(xor)) res[i] = oddCnt / 2 <= k } return res } ``` Last modification：July 11, 2025 © Allow specification reprint Support Appreciate the author AliPayWeChat Like 如果觉得我的文章对你有用，请随意赞赏
