LeetCode 1177. 构建回文串检测

约 5 分钟
文章信息 6 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节
标签
数组 字符串 哈希表 位运算 前缀和

题目描述

✅ 1177. 构建回文串检测

image-20260929075258348

image-20260929075258436

题意分析

对每个查询 [left, right, k]，单独考虑原字符串的这个闭区间。可以任意重排其中字符，并至多把 k 个字符各替换为某个小写字母，判断是否能得到回文串。

重排不消耗替换次数，替换按单个字符计数，不是一次修改该字母的所有出现。各查询相互独立，不会把某次查询假设的修改写回原串，所以可以共享一次预处理。

解法：前缀奇偶掩码

核心思路

[!blue]

能任意重排后，只需关心各字母的次数奇偶。回文两侧的字符成对出现，偶数长度时所有次数都必须为偶数，奇数长度时最多允许一种奇数次数字母放在中心。设当前出现奇数次的字母有 odd 种，它与区间长度一定同奇偶，因为偶数次数不影响总长度的奇偶性。

一次替换至多改变两种字母的奇偶性，所以最多消去两种奇数次数，这是所需操作数的下界。同时也确实能做到：从两种奇数次字母中取一份，把它替换成另一种，两者的次数就都变成偶数。将奇数种类两两配对，偶数长度全部消去，奇数长度留下一个中心，最少需要 floor(odd / 2) 次。

因为只要奇偶性，不需要保存完整次数。用二十六位整数掩码表示前缀状态，某一位为一表示对应字母出现奇数次；每读一个字符，就把该位异或翻转。pre[i] 表示前 i 个字符的状态，空前缀 pre[0] 为零。

查询闭区间 [l, r] 时，用 pre[r + 1] ^ pre[l] 抵消共同前缀，剩下恰好是区间各字母的奇偶位。统计结果中一的个数就得到 odd，再与可用替换数比较。掩码固定二十六位，每个查询都不再依赖区间长度。

解题步骤

  1. 创建长度为 n + 1 的前缀掩码数组，初值为零。
  2. 遍历字符，用上一前缀异或当前字符对应的一位，得到下一前缀状态。
  3. 对每个查询，异或右端后一位和左端的前缀状态，求出区间掩码。
  4. 统计置一位数，判断整数除法 odd / 2 <= k，按查询顺序保存结果。

代码实现

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)$，预处理原串一次，q 次查询各执行固定宽度的异或和位计数。
  • 空间复杂度：$O(n)$ 保存前缀掩码，返回结果另占 $O(q)$。

关键点总结

[!green]

  • 可重排使回文判定只剩频次奇偶，无需保留原位置关系。
  • 一次替换最多消除两个奇数种类，也总能按这种方式配对，所以下界可以达到。
  • 区间长度与奇数种类数同奇偶，向下取整自然覆盖中心位置。
  • 前缀异或消去公共部分，固定字母范围让每次查询成为常数操作。

易错点总结

[!yellow]

  • 使用 pre[r] 而不是 pre[r + 1]，会漏掉闭区间最后一个字符。
  • 先统计两个前缀的一位数再相减，不能得到区间奇偶；必须先对整个位掩码异或。
  • 将所需替换次数写成 odd，忽略一次替换可以同时修正两种奇数次数。
  • 对一半奇数种类向上取整，会错误要求替换原本能放在回文中心的那一个字符。
  • 将查询的假设修改保留给后续查询，违反它们彼此独立的要求。

相似题目

题目 难度 关联与区别
面试题 01.04. 回文排列 简单 可重排回文取决于奇数频次的种数，本题进一步允许k次替换并支持大量子串查询。
1310. 子数组异或查询 中等 用前缀异或可快速得到任意区间的奇偶位掩码，再统计奇数频次字符数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/59203057
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！