题目描述
给你一个字符串 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^50 <= queries[i][0] <= queries[i][1] < s.length0 <= queries[i][2] <= s.lengths 中只有小写英文字母
解法
方法一：前缀和
我们先考虑一个子串能否在经过最多 \(k\) 次替换后变成回文串，显然，我们需要统计子串中每个字符出现的次数，这可以通过前缀和来实现。对于出现偶数次的字符，我们不需要进行替换，对于出现奇数次的字符，我们需要进行替换，替换的次数为 \(\lfloor \frac{x}{2} \rfloor\)，其中 \(x\) 为出现奇数次的字符的个数。如果 \(\lfloor \frac{x}{2} \rfloor \leq k\)，那么这个子串就可以变成回文串。
因此，我们定义一个前缀和数组 \(ss\)，其中 \(ss[i][j]\) 表示字符串 \(s\) 的前 \(i\) 个字符中，字符 \(j\) 出现的次数。那么对于一个子串 \(s[l..r]\)，我们可以通过 \(ss[r + 1][j] - ss[l][j]\) 得到子串中字符 \(j\) 出现的次数。我们遍历所有的查询，对于每个查询 \([l, r, k]\)，我们统计子串 \(s[l..r]\) 中出现奇数次的字符的个数 \(x\)，如果 \(\lfloor \frac{x}{2} \rfloor \leq k\)，那么这个子串就可以变成回文串。
时间复杂度 \(O((n + m) \times C)\)，空间复杂度 \(O(n \times C)\)，其中 \(n\) 和 \(m\) 分别为字符串 \(s\) 和查询数组的长度；而 \(C\) 为字符集的大小，本题中字符集为小写英文字母，因此 \(C = 26\)。
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
n = len(s)
ss = [[0] * 26 for _ in range(n + 1)]
for i, c in enumerate(s, 1):
ss[i] = ss[i - 1][:]
ss[i][ord(c) - ord("a")] += 1
ans = []
for l, r, k in queries:
cnt = sum((ss[r + 1][j] - ss[l][j]) & 1 for j in range(26))
ans.append(cnt // 2 <= k)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
int n = s.length();
int[][] ss = new int[n + 1][26];
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 26; ++j) {
ss[i][j] = ss[i - 1][j];
}
ss[i][s.charAt(i - 1) - 'a']++;
}
List<Boolean> ans = new ArrayList<>();
for (var q : queries) {
int l = q[0], r = q[1], k = q[2];
int x = 0;
for (int j = 0; j < 26; ++j) {
x += (ss[r + 1][j] - ss[l][j]) & 1;
}
ans.add(x / 2 <= k);
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution {
public:
vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
int n = s.size();
int ss[n + 1][26];
memset(ss, 0, sizeof(ss));
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 26; ++j) {
ss[i][j] = ss[i - 1][j];
}
ss[i][s[i - 1] - 'a']++;
}
vector<bool> ans;
for (auto& q : queries) {
int l = q[0], r = q[1], k = q[2];
int x = 0;
for (int j = 0; j < 26; ++j) {
x += (ss[r + 1][j] - ss[l][j]) & 1;
}
ans.emplace_back(x / 2 <= k);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | func canMakePaliQueries(s string, queries [][]int) (ans []bool) {
n := len(s)
ss := make([][26]int, n+1)
for i := 1; i <= n; i++ {
for j := 0; j < 26; j++ {
ss[i][j] = ss[i-1][j]
}
ss[i][s[i-1]-'a']++
}
for _, q := range queries {
l, r, k := q[0], q[1], q[2]
x := 0
for j := 0; j < 26; j++ {
x += (ss[r+1][j] - ss[l][j]) & 1
}
ans = append(ans, x/2 <= k)
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | function canMakePaliQueries(s: string, queries: number[][]): boolean[] {
const n = s.length;
const ss: number[][] = Array(n + 1)
.fill(0)
.map(() => Array(26).fill(0));
for (let i = 1; i <= n; ++i) {
ss[i] = ss[i - 1].slice();
++ss[i][s.charCodeAt(i - 1) - 97];
}
const ans: boolean[] = [];
for (const [l, r, k] of queries) {
let x = 0;
for (let j = 0; j < 26; ++j) {
x += (ss[r + 1][j] - ss[l][j]) & 1;
}
ans.push(x >> 1 <= k);
}
return ans;
}
|