問題描述
給你一個(gè)字符串 s共螺，請(qǐng)你對(duì) s 的子串進(jìn)行檢測(cè)该肴。
每次檢測(cè)，待檢子串都可以表示為 queries[i] = [left, right, k]藐不。我們可以 重新排列 子串 s[left], ..., s[right]匀哄，并從中選擇 最多 k 項(xiàng)替換成任何小寫英文字母。
如果在上述檢測(cè)過程中佳吞，子串可以變成回文形式的字符串拱雏，那么檢測(cè)結(jié)果為 true，否則結(jié)果為 false底扳。
返回答案數(shù)組 answer[]铸抑，其中 answer[i] 是第 i 個(gè)待檢子串 queries[i] 的檢測(cè)結(jié)果。
示例
輸入：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 個(gè)字符是變不成回文串的。
queries[3] : 子串 = "abcd"木蹬，可以變成回文的 "abba"至耻。 也可以變成 "baab"，先重新排序變成 "bacd"，然后把 "cd" 替換為 "ab"尘颓。
queries[4] : 子串 = "abcda"走触，可以變成回文的 "abcba"。
解題思路
核心思路：前綴和+異或運(yùn)算
- 首先疤苹，理解題目?jī)?nèi)容：截取字符串
s中部分連續(xù)的字符互广，可以對(duì)字符進(jìn)行重新排列，并替換k個(gè)字符卧土，是否可以構(gòu)成回文字符串惫皱； - 要檢測(cè)是不是回文字符串，我們就得知道當(dāng)前截取到的字符串的組成（字母的種類及個(gè)數(shù)）尤莺；那么旅敷，自然而然的可以想到使用前綴和的方式：我們可以遍歷原字符串
s，并記錄在頭開始到每個(gè)字符位置的字符串的字母狀態(tài)（字母的種類及個(gè)數(shù)）缝裁；用后一個(gè)字母狀態(tài)減去前一個(gè)字母狀態(tài)扫皱，就可以得到截取部分的字母狀態(tài)了； - 得到了字母的組成捷绑，那么如何判斷回文字符串呢韩脑？
我們要對(duì)每種字母進(jìn)行分析，如果字母的個(gè)數(shù)是偶數(shù)粹污，那么在構(gòu)成回文字符串的時(shí)候段多，我們完全可以將這些字母均勻的放在回文字符串的兩邊；也就是說壮吩，偶數(shù)個(gè)的字母进苍，我們可以直接忽略對(duì)回文串的影響；
如果字母的個(gè)數(shù)是奇數(shù)鸭叙，那么就要進(jìn)行具體的分析：
如果奇數(shù)個(gè)的字母只有1個(gè)觉啊，仍然可以構(gòu)成回文串；
如果奇數(shù)個(gè)的字母只有2個(gè)沈贝，需要修改1個(gè)字母才能構(gòu)成回文串杠人；
如果奇數(shù)個(gè)的字母只有3個(gè)，仍然是需要修改1個(gè)字母才能構(gòu)成回文串宋下；
也就是說嗡善，如果奇數(shù)個(gè)的字母為n個(gè)，需要修改2/n個(gè)字母才能構(gòu)成回文串学歧。 - 優(yōu)化：異或運(yùn)算
在上述的步驟中罩引，我們統(tǒng)計(jì)了字母的種類及其個(gè)數(shù)；其實(shí)枝笨，我們并不需要知道具體的數(shù)量袁铐，需要知道的是字母?jìng)€(gè)數(shù)的奇偶變化揭蜒；如果奇變奇、偶變偶昭躺，那么可能沒有變化忌锯，也有可能多了偶數(shù)個(gè)伪嫁，對(duì)回文串的構(gòu)成沒有影響领炫；如果是奇偶互變，那么肯定是發(fā)生了奇數(shù)個(gè)的變化张咳，統(tǒng)計(jì)變化的數(shù)量即可帝洪。
另外，我們現(xiàn)在使用一個(gè)長(zhǎng)為26位的數(shù)組來存放了字母的個(gè)數(shù)脚猾，我們可以對(duì)此進(jìn)行優(yōu)化：將數(shù)組壓縮為一個(gè)二進(jìn)制數(shù)進(jìn)行存放葱峡。
那么在遍歷字符串s，如何修改某個(gè)字母的個(gè)數(shù)狀態(tài)（現(xiàn)在只存奇偶）呢龙助？
修改a出現(xiàn)的數(shù)量時(shí)砰奕，與二進(jìn)制數(shù)1進(jìn)行異或；
修改b出現(xiàn)的數(shù)量時(shí)提鸟，與二進(jìn)制數(shù)10進(jìn)行異或军援；
修改c出現(xiàn)的數(shù)量時(shí)，與二進(jìn)制數(shù)100進(jìn)行異或称勋；
修改d出現(xiàn)的數(shù)量時(shí)胸哥，與二進(jìn)制數(shù)1000進(jìn)行異或；
以此類推...
代碼示例（JAVA）
初步代碼赡鲜，使用前綴和
class Solution {
public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
int len = s.length();
int[][] arr = new int[len + 1][26];
// 統(tǒng)計(jì)前綴和
for (int i = 0; i < len; i++) {
char c = s.charAt(i);
arr[i + 1] = arr[i].clone();
arr[i + 1][c - 'a']++;
}
List<Boolean> res = new ArrayList<>();
for (int[] query : queries) {
int left = query[0], right = query[1], k = query[2];
// 統(tǒng)計(jì)奇數(shù)的數(shù)量
int count = 0;
for (int i = 0; i < 26; i++) {
if ((arr[right + 1][i] - arr[left][i]) % 2 != 0) {
count++;
}
}
// 添加結(jié)果
res.add(count / 2 <= k);
}
return res;
}
}
優(yōu)化：前綴和+異或運(yùn)算
class Solution {
public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
int len = s.length();
int[] arr = new int[len + 1];
// 統(tǒng)計(jì)前綴和
for (int i = 0; i < len; i++) {
int b = 1 << (s.charAt(i) - 'a');
arr[i + 1] = arr[i] ^ b;
}
List<Boolean> res = new ArrayList<>();
for (int[] query : queries) {
int left = query[0], right = query[1], k = query[2];
// 統(tǒng)計(jì)奇數(shù)的數(shù)量
int count = Integer.bitCount(arr[right + 1] ^ arr[left]);
// 添加結(jié)果
res.add(count / 2 <= k);
}
return res;
}
}
