1177. 构建回文串检测

ITCharge大约 5 分钟

---

1177. 构建回文串检测

标签：位运算、数组、哈希表、字符串、前缀和
难度：中等

题目链接

1177. 构建回文串检测 - 力扣

题目大意

描述：给定一个字符串 $s$ ，然后给你一系列查询 $queries$ 。每个查询 $[left, right, k]$ 的意思是：

从 $s$ 中截取子串 $s[left...right]$ 。
你可以重新排列这个子串里的字母（想怎么排都行）。
你还可以把最多 $k$ 个字母换成其他任意小写字母。
问：经过这两步操作后，能否把这个子串变成一个回文串（正着读和反着读一样）？

注意每次查询是独立的，不修改原始字符串 $s$ 。

要求：返回一个布尔数组， $answer[i]$ 表示第 $i$ 个查询的结果。

说明：

$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$ 中只有小写英文字母。

示例：

输入：s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
输出：[true,false,false,true,true]
解释：
query[0]：子串 "d"，本身已经是回文 → true
query[1]：子串 "bc"，不是回文，且不能替换 → false
query[2]：子串 "abcd"，只能替换 1 个，变不成回文 → false
query[3]：子串 "abcd"，可以替换 2 个，变成 "abba" → true
query[4]：子串 "abcda"，替换 1 个，变成 "abcba" → true

解题思路

思路 1：前缀和 + 位运算

这道题的核心是要快速判断一个子串能否变成回文。

先回顾一下回文串的规律：

回文串就是正着读反着读一样的串。比如说 "abba"，从左往右和从右往左读都是 "abba"。

什么样的情况下一个字符串能排成回文？

如果字符串长度是偶数：每种字母必须出现偶数次（因为要两两配对，左右对称）。
如果字符串长度是奇数：最多允许一种字母出现奇数次（放在最中间当「中心」），其他字母都必须是偶数次。

比如 "aab"：a 出现 2 次（偶数），b 出现 1 次（奇数），可以排成 "aba"。

所以问题转化为： 对于一个子串，统计有多少种字母出现了奇数次。假设有 $odd$ 种奇数字母，那么：

每替换 1 个字母，可以消除 2 个奇数字母（比如把出现奇数次的 b 改成出现奇数次的 c，相当于两个字符都变成偶数次）。
所以至少需要替换 $\lfloor odd / 2 \rfloor$ 个字母才能变成回文。
只要 $\lfloor odd / 2 \rfloor \le k$ ，就可以做到。

问题又转化为：如何快速知道一个子串里每种字母出现次数的奇偶性？

暴力方法是对每个查询去数一遍子串里的字母，但字符串和查询都可能长达 $10^5$ ，太慢了。

高效方法：前缀和 + 位运算

技巧是这样的：

用二进制位表示奇偶性。 26 个小写字母对应 26 个二进制位。某一位为 1 表示这个字母出现了奇数次，0 表示偶数次。比如 0000...0001 表示 a 出现了奇数次。
用异或（XOR）运算快速更新状态。 如果字母是第 $i$ 个，就把第 $i$ 位翻转（1 变 0，0 变 1）。因为有这样一个规律：偶数次 + 1 次 = 奇数次，奇数次 + 1 次 = 偶数次，正好对应异或运算。
用前缀和思想。 预处理一个数组 prefix，其中 prefix[i] 表示从开头到位置 $i-1$ 的奇偶性状态。那么子串 $s[left...right]$ 的状态 = prefix[right+1] ^ prefix[left]（因为异或可以把前缀部分抵消掉）。

用人话比喻：这就像在考勤表上记录每个字母「已经出现了奇数次还是偶数次」，然后通过两个时间点的记录做异或，就能知道中间这段时间的变化。

步骤拆解：

预处理阶段（一次遍历）：
- 初始化 prefix[0] = 0。
- 遍历字符串 $s$ 的每个字符，用异或把当前字符对应的位翻转，得到 prefix[i+1]。
查询阶段：
- 对于每个查询 [left, right, k]，通过 prefix[right+1] ^ prefix[left] 得到子串的奇偶性状态。
- 统计这个状态中有多少个 1（也就是出现了奇数次的字母种类数）。
- 如果 1 的个数 // 2 <= k，这个子串就能变成回文。

思路 1：代码

class Solution:
    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        n = len(s)
        # 前缀和数组，prefix[i] 表示 s[0:i] 的奇偶性状态（不含位置 i）
        # 用一个整数的低 26 位代表 26 个字母的奇偶性
        prefix = [0] * (n + 1)
        
        # 预处理：遍历字符串，逐步构建前缀和
        for i in range(n):
            # 1 << (ord(s[i]) - ord('a')) 把当前字母对应的二进制位设为 1
            # 异或运算：如果之前是 0 变成 1（奇数次），是 1 变成 0（偶数次）
            prefix[i + 1] = prefix[i] ^ (1 << (ord(s[i]) - ord('a')))
        
        result = []
        for left, right, k in queries:
            # 用两个前缀状态异或，得到子串 s[left:right+1] 的奇偶性
            state = prefix[right + 1] ^ prefix[left]
            # 统计 state 中有多少个 1（即出现奇数次的字母种类数）
            odd_count = bin(state).count('1')
            # 每替换 1 个字母可以消除 2 个奇数，所以需要 odd_count // 2 <= k
            result.append(odd_count // 2 <= k)
        
        return result

思路 1：复杂度分析

时间复杂度： $O(n + m)$ 。用人话说就是：预处理阶段遍历一遍字符串 $s$ （长度 $n$ ），每个查询只需常数时间（ $m$ 个查询），非常快。
空间复杂度： $O(n)$ 。需要存储长度为 $n+1$ 的前缀和数组。