LeetCode 1177. 构建回文串检测

2023-08-19 HGNULB 约 11 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 1177. 构建回文串检测

题意分析

给定字符串 s 和若干查询 [left, right, k]。对每个查询，取出子串 s[left..right]，允许任意重排其中的字符，并且可以把其中至多 k 个字符替换成任意字母，问能否把它变成回文串。对每个查询返回一个布尔值。

三个规则要逐一读准。第一，可以任意重排——这句话把「字符的位置」这个维度整个消掉了，只剩下「每个字母各有多少个」这一份信息。第二，替换是任意的，替换后的字符不受原串限制，也就是说一次替换可以把任何一个字母变成任何我们想要的字母。第三，k 是上限而非精确次数，用不满也可以。

每个查询彼此独立，且不会真的修改 s——这一点决定了可以对 s 做一次全局预处理，之后每个查询只读不写。

约束是本题的关键信号：s 长度和查询数都可达 $10^5$。$O(n \cdot q) = 10^{10}$ 必然超时，所以每个查询必须在近似 $O(1)$ 的时间内回答，这就要求把「子串的字符信息」预处理成可 $O(1)$ 提取的形式。同时字符集只有 26 个小写字母——这个小到可以塞进一个整数的位数，是后面用位掩码的直接依据。

边界：left 可能等于 right（长度为 1 的子串，本身就是回文，答案恒 true）；k 可能为 0（不允许替换）；k 可能大于子串长度（怎么都能拼成回文，恒 true）。

解法：前缀奇偶掩码

核心思路

先把问题从字符串化简成计数。因为可以任意重排，一个字符多重集能排成回文的充要条件是：出现奇数次的字母最多有一个（长度为偶数时必须是 0 个，奇数时恰好 1 个）。

那么允许 k 次替换时呢？设子串里出现奇数次的字母共有 odd 个。一次替换至多翻转两个字母的奇偶性，因此至多消掉两个奇数，至少需要 $\lfloor odd/2 \rfloor$ 次；反过来，每次把一个奇数字母改成另一个奇数字母，就能把它们成对消掉，确实能在这么多次内完成。剩下至多一个奇数字母放在回文中心，所以最少替换次数恰为 $\lfloor odd/2 \rfloor$，判定条件就是：
\[\left\lfloor \frac{odd}{2} \right\rfloor \le k\]
这个式子对长度奇偶两种情况都成立，不需要分类讨论——长度为偶数时 odd 必为偶数，odd/2 次替换刚好清零；长度为奇数时 odd 必为奇数，odd/2 向下取整后留下一个奇数字母坐镇中心。能一句话说清「为什么不用讨论长度奇偶」，是这道题最值得展示的推理。

现在问题变成：如何在 $O(1)$ 内求出任意子串的 odd？

暴力是对每个查询开 26 个计数器扫一遍子串，$O(26 + len)$，总计 $O(nq)$，超时。瓶颈在于重复统计了大量重叠区间。

自然的想法是前缀和：开 pre[i][c] 记录前 i 个字符中字母 c 的个数，区间计数用相减得到。这能做到每次查询 $O(26)$，$26 \times 10^5$ 也能过，但空间是 $O(26n)$。

再进一步观察：判定只用到每个字母出现次数的奇偶性，具体次数完全无关。于是每个字母只需 1 个比特，26 个字母恰好压进一个 int：

pre[i] = 前 i 个字符中，各字母出现次数奇偶性的 26 位掩码（第 c 位为 1 表示字母 c 出现了奇数次）。

递推是 pre[i+1] = pre[i] ^ (1 << (s[i] - 'a'))——异或天然就是「翻转一位」，与奇偶性的语义完美对应。

区间提取靠异或的自反性：$x \oplus x = 0$。前缀 pre[l] 在 pre[r+1] 中被算了一遍，异或一次正好抵消，于是
\[mask_{[l,r]} = pre[r+1] \oplus pre[l]\]
这个掩码里 1 的个数就是 odd，用 Integer.bitCount 一步求出。整个查询 $O(1)$。

不变量是：pre[i] 恒等于 s[0..i-1] 的奇偶掩码，pre[0] = 0 表示空前缀（所有字母出现 0 次，全偶）。 前缀数组长度取 n + 1，正是为了给空前缀留一个位置，从而让 l = 0 的查询无需特判。

正确性：由前缀不变量和异或抵消，pre[r+1] ^ pre[l] 精确表示子串 [l,r] 的字符奇偶性，位数 odd 因而准确。一次替换至多消去两个奇数频次，所以少于 odd/2 次一定不够；把奇数字符两两替换又能恰用 odd/2 次完成，剩余至多一个放在中心。因此 odd / 2 <= k 是可构成回文的充要条件，每个查询的判定都正确。

解题步骤

开长度 n + 1 的前缀数组，pre[0] = 0。多开的这一位代表空前缀，它让区间公式对 l = 0 同样成立——若只开 n 位，pre[l] 在 l = 0 时就没有对应项，必须写特判。

递推构建：pre[i+1] = pre[i] ^ (1 << (s.charAt(i) - 'a'))。用异或而不是加法：只关心奇偶，异或让同一字母出现两次自动归零，省掉取模。1 << (c - 'a') 把字母映射到 0 到 25 号比特位。

逐查询取区间掩码：mask = pre[r + 1] ^ pre[l]。右端用 r + 1 是因为 pre 的下标含义是「前多少个字符」，闭区间 [l, r] 对应前缀差 pre[r+1] - pre[l]。写成 pre[r] ^ pre[l] 会漏掉最后一个字符。

数 1 的个数：odd = Integer.bitCount(mask)（Go 用 bits.OnesCount）。掩码里为 1 的比特恰好对应「在该区间内出现奇数次」的字母。

判定：res.add(odd / 2 <= k)。整数除法即向下取整，这一行同时覆盖了奇偶两种长度。

按顺序收集结果返回，与 queries 一一对应。

以 s = "abcda"、queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]] 走一遍（答案 [true, false, false, true, true]）：

先建前缀掩码（用二进制的低 5 位表示 a..e，最右为 a）：pre[0] = 00000；读 a → pre[1] = 00001；读 b → pre[2] = 00011；读 c → pre[3] = 00111；读 d → pre[4] = 01111；读 a → pre[5] = 01110（a 出现两次，回到偶数）。

查询 [3,3,0]：mask = pre[4] ^ pre[3] = 01111 ^ 00111 = 01000，odd = 1（只有 d），1 / 2 = 0 <= 0，true。单字符子串本身就是回文，与直觉一致。

查询 [1,2,0]：mask = pre[3] ^ pre[1] = 00111 ^ 00001 = 00110，odd = 2（b 与 c），2 / 2 = 1 > 0，false。子串 "bc" 不改字符无论怎么排都不是回文。

查询 [0,3,1]：mask = pre[4] ^ pre[0] = 01111，odd = 4（a b c d 各一次），4 / 2 = 2 > 1，false。四个不同字母要两次替换才能凑成回文，只给 1 次不够。

查询 [0,3,2]：同样 odd = 4，2 <= 2，true。比如把 c 换成 b、d 换成 a，得到 abba。

查询 [0,4,1]：mask = pre[5] ^ pre[0] = 01110，odd = 3（b c d，a 出现两次是偶数），3 / 2 = 1 <= 1，true。子串 "abcda" 长度为 5，把 c 换成 b 得到 {a,a,b,b,d}，排成 abdba。注意这里 odd = 3 向下取整成 1 而不是 2——多出来的那个奇数字母正好占据回文中心，这就是「不必讨论长度奇偶」的具体体现。

若把区间写成 pre[r] ^ pre[l]，查询 [0,4,1] 会算成 pre[4] ^ pre[0] = 01111，odd = 4，判定变成 2 <= 1 即 false，与正确答案相反。

代码实现

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

class Solution {
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        int n = s.length();
        // pre[i] 是 s[0..i-1] 各字母出现次数奇偶性的 26 位掩码，pre[0] 代表空前缀。
        int[] pre = new int[n + 1];
        for (int i = 0; i < n; i++) {
            int bit = 1 << (s.charAt(i) - 'a');
            pre[i + 1] = pre[i] ^ bit;
        }

        List<Boolean> res = new ArrayList<>(queries.length);
        for (int[] q : queries) {
            int l = q[0];
            int r = q[1];
            int k = q[2];

            // 异或自反，公共前缀 pre[l] 被抵消，剩下的正是区间 [l, r] 的奇偶信息。
            int mask = pre[r + 1] ^ pre[l];
            int odd = Integer.bitCount(mask);
            // 奇数字母两两配对消除，向下取整同时覆盖了长度为奇数的情况。
            res.add(odd / 2 <= k);
        }
        return res;
    }
}

import "math/bits"

func canMakePaliQueries(s string, queries [][]int) []bool {
	n := len(s)
	// pre[i] 是 s[0..i-1] 各字母出现次数奇偶性的 26 位掩码，pre[0] 代表空前缀。
	pre := make([]int, n+1)
	for i := 0; i < n; i++ {
		bit := 1 << (s[i] - 'a')
		pre[i+1] = pre[i] ^ bit
	}

	res := make([]bool, len(queries))
	for i, q := range queries {
		l, r, k := q[0], q[1], q[2]
		// 异或自反，公共前缀 pre[l] 被抵消，剩下的正是区间 [l, r] 的奇偶信息。
		mask := pre[r+1] ^ pre[l]
		odd := bits.OnesCount(uint(mask))
		// 奇数字母两两配对消除，向下取整同时覆盖了长度为奇数的情况。
		res[i] = odd/2 <= k
	}
	return res
}

复杂度分析

时间复杂度：$O(n + q)$，其中 $n$ 为字符串长度、$q$ 为查询数。预处理线性扫描一次；每个查询只处理一个固定宽度的整数掩码，因此是 $O(1)$。

空间复杂度：$O(n)$，前缀掩码数组占 n + 1 个 int；相比 int[n+1][26] 的二维前缀和省了 26 倍。返回的结果数组 $O(q)$ 通常不计入。

关键点总结

「可以任意重排」等价于「只保留字符计数、丢弃位置」，这是回文类题目最常见的第一步化简。

回文的判定只依赖各字母出现次数的奇偶性，不依赖具体次数——识别出「只需要 1 比特信息」是把二维前缀和压成一维位掩码的依据。

一次替换能同时翻转两个字母的奇偶性，所以消除 odd 个奇数字母需要 $\lfloor odd/2 \rfloor$ 次；向下取整让长度为奇数的情形自然成立，无需分类讨论。

异或的自反性 $x \oplus x = 0$ 使它成为「奇偶前缀和」的天然运算，区间值就是两端前缀的异或。

前缀数组开 n + 1 位、pre[0] 留给空前缀，是让 l = 0 免特判的标准做法。

字符集大小 ≤ 32 时优先考虑位掩码压缩状态，bitCount 是配套的常数级统计工具。

面试视角：答题路径应是「重排 ⇒ 只看计数 ⇒ 只看奇偶 ⇒ 位掩码 ⇒ 异或前缀」，一步步把信息量削下去。面试官常追问「为什么是 odd/2 而不是 (odd-1)/2 或 odd/2 后还要判长度奇偶」，能用「一次替换消两个奇数」和「中心可留一个」两句话答清楚，就拿到了这题的核心分。

易错点总结

错误写法：区间掩码写成 pre[r] ^ pre[l]。用例 s = "abcda"、查询 [0,4,1]：漏掉最后一个字符，odd 算成 4，判定为 false，而正确答案是 true。

错误写法：区间掩码写成 pre[r+1] ^ pre[l-1]（把闭区间左端也多减一位）。用例 s = "aabc"、查询 [1,2,0]：正确子串 "ab" 有 2 个奇数字母，应返回 false；错误公式算入 s[0] 后得到 "aab" 的奇偶性，误判为 true，且 l = 0 时还会越界。

错误写法：判定写成 odd <= k。用例 s = "abcda"、查询 [0,3,2]：odd = 4，4 <= 2 为假返回 false，而正确答案是 true——忽略了一次替换能消掉两个奇数字母。

错误写法：判定写成 (odd + 1) / 2 <= k（向上取整）。用例查询 [3,3,0]：odd = 1，向上取整得 1 > 0 返回 false，而单字符子串显然是回文，正确答案是 true。

错误写法：额外按子串长度奇偶做分支，例如长度为偶数时要求 odd == 0。用例查询 [0,3,2]：odd = 4 不为 0 被判 false，而允许 2 次替换后完全可行，正确答案是 true。

错误写法：前缀数组只开 n 位。用例查询 [0,4,1]：访问 pre[5] 越界；若改成 pre[r] 又会丢字符，两头不讨好。

错误写法：用加法前缀和记次数后再逐字母取模求奇偶，但忘记开 26 维而只用一个总计数。用例任意子串：总字符数的奇偶与「多少个字母出现奇数次」毫无关系，判定完全失效。

错误写法：对每个查询重新扫一遍子串统计 26 个计数。用例 $n = q = 10^5$ 且区间都很长：$10^{10}$ 次操作直接超时，必须预处理。

错误写法：位移写成 1 << s.charAt(i)（忘了减 'a'）。用例任意小写字母串：移位量达 97 以上，在 Java 中会按 32 取模得到错乱的比特位，不同字母互相碰撞，结果错误且难以察觉。

错误写法：用 Integer.bitCount(pre[r+1]) - Integer.bitCount(pre[l]) 代替先异或再计数。用例 s = "abcda"、查询 [1,4,1]：pre[5] = 01110 有 3 个 1、pre[1] = 00001 有 1 个 1，相减得 2；而真实掩码 01110 ^ 00001 = 01111 有 4 个 1。比特计数不满足减法，只要某一位在两端取值不同就会算错。

错误写法：把 k 当成「必须恰好替换 k 次」。用例 s = "abba"、查询 [0,3,2]：子串已经是回文，无需替换，题目允许不用满，正确答案仍是 true。

相似题目

题目	难度	考察点
409. 最长回文串	简单	同为「重排成回文」的计数判定，但求的是能拼出的最大长度
面试题 01.04. 回文排列	简单	只判断整串能否重排成回文，是本题去掉区间与替换后的最小内核
1400. 构造 K 个回文字符串	中等	把字符分配到 `k` 个回文串中，判定条件变成奇数字母数与 `k` 的夹逼
1542. 找出最长的超赞子字符串	困难	同用奇偶掩码前缀，但改为哈希表记录首次出现位置以求最长合法区间
1310. 子数组异或查询	中等	异或前缀和的纯粹模板题，帮助固化 `pre[r+1] ^ pre[l]` 的下标含义
303. 区域和检索 - 数组不可变	简单	加法版前缀和，与异或版对照可看清「运算需可逆」这一共同前提