题目描述
给定一个字符串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，可以认为每次检测都是独立的）
提示：
- 1 <= s.length, queries.length <= 10^5
- 0 <= queries[i][0] <= queries[i][1] < s.length
- 0 <= queries[i][2] <= s.length
- s 中只有小写英文字母
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/can-make-palindrome-from-substring
分析
我们可以做两个操作，即重新排列和替换最多k项为任意小写字母。既然可以重新排列，那么我们肯定想的是把重复的字母给他按照中心对称排列，剩下的就是出现单数的字母了，比如出现了3次b，那么我们可以取2个b对称排列，剩下一个b，到最后就会变成一个回文字符串和其余的个数为1的字母了，我们只要把这些单个的字母转换成回文就好。我们可以进行k次转换，假设单个字母的个数为n，由于这些字母互不相同，所以只要k >= n / 2就可以保证能够转换为回文，反之不行。
但是如果对每一个query都进行如上操作，会出现超时，所以我们对字符串s进行预处理，计算出0-i的子串包含字母c的次数，使用动态规划。
代码
实现如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| import java.util.ArrayList;
class Solution {
public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
int[][] dp = new int[s.length()][26];
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j < 26; j++) {
if (i == 0) {
dp[i][s.charAt(i) - 'a'] = 1;
} else {
dp[i][j] = dp[i - 1][j] + ((s.charAt(i) - 'a') == j? 1: 0);
}
}
}
List<Boolean> result = new ArrayList<Boolean>();
if (queries == null) {
return result;
}
for (int[] query : queries) {
int start = Math.min(Math.max(0, query[0]), s.length() - 1);
int end = Math.min(Math.max(0, query[1]), s.length() - 1);
int k = query[2];
if (k >= (end - start + 1) / 2) {
result.add(true);
continue;
}
int count = 0;
for (int i = 0; i < 26; i++) {
int c = 0;
if (start == 0) {
c = dp[end][i];
} else {
c = dp[end][i] - dp[start - 1][i];
}
if (c % 2 == 1) {
count++;
}
}
result.add(k >= count / 2);
}
return result;
}
}
|