JZX轻语：简
LeetCode 1177 - 构建回文串检测
发表于2024年07月05日
一开始理解错题目了，题目原意是可以打乱子数组的。因此，我们仅需统计子数组内各个字符出现的次数。如果字符串是回文的，则最多只有一个字符的出现次数为奇数。此类的区间查询题目可使用前缀和的方式解决，维护前缀各个字符出现的次数，通过相减快速计算任意子数组内各字符出现的次数。该题目有两个关注点：1. 字符串是否回文仅关注每个字符出现次数的奇偶性，我们可以将前缀的字符计数信息压缩为一个整数，通过位异或运算即可得到任意子数组各字符计数的奇偶性，简化相减步骤；2. 由于题目允许k次修改，如果奇数字符个数除以2的结果(向下取整)小于等于k，则可修改成回文串。
对于第1个关注点，不难得知奇数-奇数=偶数，奇数-偶数=奇数, 偶数-偶数=偶数，符合异或计算的规律，因此，我们可以使用第i个比特位来表示第i个小写字母奇数的奇偶性，其中1表示奇数，0表示偶数，通过异或运算得到任意子数组的字符计数奇偶性。
对于第2个关注点，如果奇数字符个数为1，则满足回文串条件，无需修改；如果为2，则需要修改1次(将其中一个奇数字符改成另一个即可)；如果为3，则需要修改1次(其中一个固定在中间，另外两个将其中一个改成另一个即可)；如果为4，则需要修改2次(将其中两个奇数字符改成另外两个即可)。综上，我们可以通过奇数字符个数//2来计算需要修改的次数。
class Solution:
def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
ord_a = ord('a')
prev_patterns = [0] * len(s)
prev = 0
for i, ch in enumerate(s):
# 通过异或计算更新字符计数的奇偶性
prev_patterns[i] = prev = prev ^ (1 << (ord(ch) - ord_a))
ans = []
for l, r, k in queries:
# 通过异或计算相减两个前缀信息即可得到任意子数组的字符计数奇偶性
interval_pattern = prev_patterns[r] ^ (prev_patterns[l - 1] if l > 0 else 0)
# 统计1的个数，即奇数字符的个数, 需要至少修改的次数为奇数字符个数//2
ans.append(interval_pattern.bit_count() // 2 <= k)
return ans