构建回文串检测

难度: Medium

给你一个字符串 s，请你对 s 的子串进行检测。

每次检测，待检子串都可以表示为 queries[i] = [left, right, k]。我们可以 重新排列 子串 s[left], ..., s[right]，并从中选择最多 k 项替换成任何小写英文字母。

如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为 true，否则结果为 false。

返回答案数组 answer[]，其中 answer[i] 是第 i 个待检子串 queries[i] 的检测结果。

注意：在替换时，子串中的每个字母都必须作为 独立的 项进行计数，也就是说，如果 s[left..right] = "aaa" 且 k = 2，我们只能替换其中的两个字母。（另外，任何检测都不会修改原始字符串 s，可以认为每次检测都是独立的）

示例：

输入：s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
输出：[true,false,false,true,true]
解释：
queries[0] : 子串 = "d"，回文。
queries[1] : 子串 = "bc"，不是回文。
queries[2] : 子串 = "abcd"，只替换 1 个字符是变不成回文串的。
queries[3] : 子串 = "abcd"，可以变成回文的 "abba"。 也可以变成 "baab"，先重新排序变成 "bacd"，然后把 "cd" 替换为 "ab"。
queries[4] : 子串 = "abcda"，可以变成回文的 "abcba"。

提示：

1 <= s.length, queries.length <= 10^5
0 <= queries[i][0] <= queries[i][1] < s.length
0 <= queries[i][2] <= s.length
s 中只有小写英文字母

Submission

运行时间: 102 ms

内存: 55.7 MB

class Solution:
    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        n = len(queries)
        ans = []
        cnt = [0]
        for x in s:
            bit = 1 << (ord(x) - ord("a"))
            cnt.append(cnt[-1] ^ bit)
        
        for l, r, k in queries:
            m = (cnt[r + 1] ^ cnt[l]).bit_count()
            ans.append(m // 2 <= k)
        return ans

Explain

题解使用了前缀XOR和位运算来有效地处理查询。首先，它通过记录每个字符的位向量（一个长度为26的位向量，每位表示一个字母是否出现奇数次）的前缀XOR数组cnt来处理字符串s。这样，任何子串s[l...r]的奇偶位图可以通过cnt[r+1] XOR cnt[l]快速获得。每个查询检查通过计算此XOR结果中置位的数量（即奇数字符的个数），然后判断是否可以通过至多k次替换使奇数个数的字符变为偶数个，从而形成回文串。

时间复杂度: O(n + q)

空间复杂度: O(n)

class Solution:
    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        n = len(queries)
        ans = []
        cnt = [0]  # 初始化前缀XOR数组，起始元素为0
        for x in s:  # 遍历字符串s
            bit = 1 << (ord(x) - ord('a'))  # 计算当前字符的位向量
            cnt.append(cnt[-1] ^ bit)  # 计算到当前字符为止的前缀XOR
        
        for l, r, k in queries:  # 处理每一个查询
            m = (cnt[r + 1] ^ cnt[l]).bit_count()  # 计算子串s[l...r]的奇数字符数量
            ans.append(m // 2 <= k)  # 判断是否能通过至多k次替换成回文串
        return ans

Explore

前缀XOR数组通过对每个字符进行位运算来构建，每个字符被转换为一个长度为26的位向量，其中的每一位代表一个字母（从a到z），该位为1表示该字母出现奇数次，为0表示出现偶数次。当使用XOR操作更新前缀数组时，如果一个字符在新的位置再次出现，它的对应位会再次翻转（即从1变为0或从0变为1）。这样，通过XOR操作，前缀数组的每个元素都能正确地表示从字符串开始到当前位置所有字符的奇偶性。对于任何子串s[l...r]，通过计算cnt[r+1] XOR cnt[l]，我们可以得到子串中每个字符出现次数的奇偶性，因为XOR操作会消除出现偶数次的字符的影响（因为两次相同的翻转会抵消掉），只留下奇数次出现的字符的影响。

在前缀XOR数组中，每个元素都记录了从字符串开始到该点的所有字符的出现次数的奇偶性。当我们计算cnt[r+1] XOR cnt[l]时，实际上是将从开始到位置l的所有字符的奇偶性信息与从开始到位置r+1的所有字符的奇偶性信息进行XOR操作。这种操作的性质是，相同的奇偶性信息（对于同一个字符出现偶数次）会相互抵消，只留下那些在子串s[l...r]中奇数次出现的字符。因此，结果中的每一个置位（即值为1的位）都直接指示了在对应位置的字符在s[l...r]中出现了奇数次。

具体的位运算过程如下：首先，将每个字符映射到一个位向量中的一个具体的位。例如，字符'a'对应的位向量是1（即00000000000000000000000001），字符'b'对应的位向量是2（即00000000000000000000000010），依此类推。每当字符x出现时，我们将其对应的位向量与前缀XOR数组的最后一个元素进行XOR操作。这个操作的作用是，如果该位原先为0（表示对应字符出现了偶数次或未出现），它会变为1（现在出现奇数次），反之亦然。因此，每次XOR操作都会更新前缀XOR数组以反映当前字符的出现次数的奇偶性变化。这样构建的前缀XOR数组，可以通过简单的XOR操作来查询任意子串中字符的奇偶次数状态。