题目描述
给你一个字符串 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
中只有小写英文字母。
算法
(前缀和,找规律) $O(n + q)$
- 对于每次询问,统计区间内出现次数为奇数的字母的个数 $t$。
- 如果 $k \ge t / 2$,则我们可以通过替换将其变成回文串。这是因为,出现次数为偶数的字母我们不需要担心;出现次数为奇数的字母,我们替换其中的一半(如果长度为奇数则替换一半的下取整)则可以将他们配对。
- 为了快速求出区间内每个字母出现的次数,我们通过前缀和数组 $ch(i, j)$,记录前 $i$ 个字母中,字母 $j$ 出现的次数。
- 每次询问,求出区间
[l, r]
内的字母个数。
时间复杂度
- 预处理需要 $O(n)$ 的时间,每次询问枚举 26 个字母,故时间复杂度为 $O(n + q)$。
空间复杂度
- 需要数组空间记录前缀和,故空间复杂度为 $O(n)$。
C++ 代码
class Solution {
public:
vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
int n = s.length();
vector<bool> ans;
vector<vector<int>> ch(n + 1, vector<int>(26, 0));
for (int i = 1; i <= n; i++)
for (int j = 0; j < 26; j++)
if (s[i - 1] - 'a' == j)
ch[i][j] = ch[i - 1][j] + 1;
else
ch[i][j] = ch[i - 1][j];
for (auto& q: queries) {
int l = q[0], r = q[1], k = q[2];
int t = 0;
for (int i = 0; i < 26; i++)
if ((ch[r + 1][i] - ch[l][i]) & 1)
t++;
ans.push_back(k >= t / 2);
}
return ans;
}
};