Medium

题目描述

给你一个字符串 s 和一个查询数组 queries，其中 queries[i] = [lefti, righti, ki]。

对于每个查询，你可以重新排列子字符串 s[lefti...righti]，然后选择其中至多 ki 个字符替换为任意小写英文字母。

如果经过上述操作后，子字符串能够变成回文串，那么查询的结果为 true，否则为 false。

返回一个布尔数组 answer，其中 answer[i] 是第 i 个查询 queries[i] 的结果。

注意：

  • 每个字母都单独计算替换次数，例如如果 s[lefti...righti] = "aaa" 且 ki = 2，我们只能替换其中两个字母
  • 没有查询会修改初始字符串 s

示例 1：

输入：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" 构成回文串。
queries[4]: 子字符串 = "abcda"，可以变成 "abcba" 构成回文串。

示例 2：

输入：s = "lyb", queries = [[0,1,0],[2,2,1]]
输出：[false,true]

约束条件：

  • 1 <= s.length, queries.length <= 10^5
  • 0 <= lefti <= righti < s.length
  • 0 <= ki <= s.length
  • s 由小写英文字母组成

解题思路

这个问题的关键在于理解回文串的特性：一个字符串能构成回文串，当且仅当最多只有一个字符出现奇数次。

核心思路：

  1. 由于可以重新排列子字符串，我们只需要关注每个字符的出现频次
  2. 使用前缀和思想预处理字符频次，实现O(1)查询任意区间的字符频次
  3. 对于每个查询，计算有多少个字符出现奇数次
  4. 如果奇数次字符个数 ≤ 2*k + 1，则可以构成回文串（每次替换可以减少2个奇数次字符，最多允许1个奇数次字符）

优化技巧： 使用位掩码优化存储。由于只有26个小写字母，可以用一个32位整数表示每个字符的奇偶性，其中第i位为1表示第i个字符出现奇数次。这样：

  • 异或运算可以快速更新字符奇偶性
  • __builtin_popcount 可以快速计算奇数次字符个数
  • 空间复杂度从O(26n)优化到O(n)

时间复杂度： 预处理O(n)，每个查询O(1)，总计O(n+m) 空间复杂度： O(n)

代码实现

class Solution {
public:
    vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
        int n = s.length();
        vector<int> prefix(n + 1, 0);
        
        // 构建前缀异或数组，每一位表示对应字符的奇偶性
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] ^ (1 << (s[i] - 'a'));
        }
        
        vector<bool> result;
        for (auto& query : queries) {
            int left = query[0], right = query[1], k = query[2];
            
            // 计算区间内每个字符的奇偶性
            int mask = prefix[right + 1] ^ prefix[left];
            
            // 计算奇数次字符的个数
            int oddCount = __builtin_popcount(mask);
            
            // 如果奇数次字符个数 <= 2*k + 1，则可以构成回文串
            result.push_back(oddCount <= 2 * k + 1);
        }
        
        return result;
    }
};

class Solution:
    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        n = len(s)
        prefix = [0] * (n + 1)
        
        # 构建前缀异或数组，每一位表示对应字符的奇偶性
        for i in range(n):
            prefix[i + 1] = prefix[i] ^ (1 << (ord(s[i]) - ord('a')))
        
        result = []
        for left, right, k in queries:
            # 计算区间内每个字符的奇偶性
            mask = prefix[right + 1] ^ prefix[left]
            
            # 计算奇数次字符的个数
            odd_count = bin(mask).count('1')
            
            # 如果奇数次字符个数 <= 2*k + 1，则可以构成回文串
            result.append(odd_count <= 2 * k + 1)
        
        return result

public class Solution {
    public IList<bool> CanMakePaliQueries(string s, int[][] queries) {
        int n = s.Length;
        int[] prefix = new int[n + 1];
        
        // 构建前缀异或数组，每一位表示对应字符的奇偶性
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] ^ (1 << (s[i] - 'a'));
        }
        
        List<bool> result = new List<bool>();
        foreach (int[] query in queries) {
            int left = query[0], right = query[1], k = query[2];
            
            // 计算区间内每个字符的奇偶性
            int mask = prefix[right + 1] ^ prefix[left];
            
            // 计算奇数次字符的个数
            int oddCount = CountBits(mask);
            
            // 如果奇数次字符个数 <= 2*k + 1，则可以构成回文串
            result.Add(oddCount <= 2 * k + 1);
        }
        
        return result;
    }
    
    private int CountBits(int n) {
        int count = 0;
        while (n > 0) {
            count++;
            n &= n - 1;
        }
        return count;
    }
}

var canMakePaliQueries = function(s, queries) {
    const n = s.length;
    const prefix = new Array(n + 1).fill(0);
    
    // 构建前缀异或数组，每一位表示对应字符的奇偶性
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] ^ (1 << (s.charCodeAt(i) - 97));
    }
    
    const result = [];
    for (const [left, right, k] of queries) {
        // 计算区间内每个字符的奇偶性
        const mask = prefix[right + 1] ^ prefix[left];
        
        // 计算奇数次字符的个数
        const oddCount = countBits(mask);
        
        // 如果奇数次字符个数 <= 2*k + 1，则可以构成回文串
        result.push(oddCount <= 2 * k + 1);
    }
    
    return result;
};

function countBits(n) {
    let count = 0;
    while (n > 0) {
        count++;
        n &= n - 1;
    }
    return count;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n + m)，其中 n 是字符串长度，m 是查询数量
空间复杂度O(n)，用于存储前缀数组

相关题目