LeetCode 1177. 构建回文串检测

Categories:

题目描述
思路分析
1. 解法一：前缀奇偶掩码（推荐）
相似题目

题目描述

✅ 1177. 构建回文串检测

思路分析

解法一：前缀奇偶掩码（推荐）

核心思路：

用 26 位二进制掩码记录每个字母出现次数的奇偶性。

预处理前缀掩码 pre[i]，表示 s[0..i-1] 的奇偶状态。

区间 [l, r] 的奇偶掩码为 pre[r+1] ^ pre[l]，其 1 的个数是奇数字母数。

需要替换的最少字符数为 odd / 2，判断 odd / 2 <= k。

复杂度分析：

时间复杂度：O(n + q)，其中 n 为字符串长度，q 为查询数量。

空间复杂度：O(n)，存储前缀掩码。

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

class Solution {
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        int n = s.length();
        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];

            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 := 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]
        mask := pre[r+1] ^ pre[l]
        odd := bits.OnesCount(uint(mask))
        res[i] = odd/2 <= k
    }
    return res
}

相似题目

题目	难度	考察点
409. 最长回文串	简单	字符计数
266. 回文排列	简单	奇偶统计
680. 验证回文串 II	简单	双指针
647. 回文子串	中等	回文统计
1312. 让字符串成为回文串的最少插入次数	困难	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/59203057