引言

今天的每日一題原題是1863. 找出所有子集的異或總和再求和，比較水，直接對于集合中的每一個元素，都有取或者不取2種情況，直接遞歸進去求和即可。更換成前幾天遇到的更有意思的一題來寫這個每日一題。

題目

有一個只含有 'Q', 'W', 'E', 'R' 四種字符，且長度為 n 的字符串。

假如在該字符串中，這四個字符都恰好出現 n/4 次，那么它就是一個「平衡字符串」。

給你一個這樣的字符串 s，請通過「替換一個子串」的方式，使原字符串 s 變成一個「平衡字符串」。

你可以用和「待替換子串」長度相同的 任何 其他字符串來完成替換。

請返回待替換子串的最小可能長度。

如果原字符串自身就是一個平衡字符串，則返回 0。

示例 1：

輸入：s = "QWER"
輸出：0
解釋：s 已經是平衡的了。

示例 2：

輸入：s = "QQWE"
輸出：1
解釋：我們需要把一個 'Q' 替換成 'R'，這樣得到的 "RQWE" (或 "QRWE") 是平衡的。

示例 3：

輸入：s = "QQQW"
輸出：2
解釋：我們可以把前面的 "QQ" 替換成 "ER"。 

示例 4：

輸入：s = "QQQQ"
輸出：3
解釋：我們可以替換后 3 個 'Q'，使 s = "QWER"。

提示：

• 1 <= s.length <= 10^5

• s.length 是 4 的倍數

• s 中只含有 'Q', 'W', 'E', 'R' 四種字符

思路

????????可以利用滑動窗口的思想來解題，由于替換進去的字符串內容是任意的，所以只要滿足選取1個字符串后，剩下的4個字符的個數都小于等于 length / 4 即可。

????????可以先存下起始時每個字符的個數，如果當前就滿足平衡條件，那么直接返回0即可。如果當前不平衡，我們嘗試從0到length枚舉替換字符的左端點，然后右端點不斷向右滑動，這樣在滑動的過程中，最右邊位置的字符個數-1，直到剩余字符滿足小于等于 length / 4 或者到達原始字符串邊界。注意這里要再判斷1次是否滿足平衡條件，因為可能是因為到達原始邊界才退出的。當滑動到某位置可以滿足平衡的時候，r - l就是我們要替換的字符串長度。最后，枚舉下1組左端點的時候，又相當于最左邊位置的字符放回原始數組中，所以不要忘記操作charNum[getIndex1234(chars[l])]++。

???????? 另外吐槽一下，這里QWER在字母表并不連續，只能寫了一個映射的方法來映射到下標0~3，否則就要開更大的數組來存，比如26。

代碼

class Solution {public int balancedString(String s) {int[] charNum = new int[4];char[] chars = s.toCharArray();for (char c : chars) {charNum[getIndex1234(c)]++;}int ans = s.length();int stand = ans / 4;if (charNum[0] == stand && charNum[1] == stand && charNum[2] == stand) {// 判斷3個就夠了，3個都是stand，最后1個一定是standreturn 0;}for (int l = 0, r = 0; l < s.length(); l++) {while (r < s.length() && !check(charNum, stand)) {// 右邊向右滑動1位，最右邊位置的字符個數-1charNum[getIndex1234(chars[r])]--;r++;}if (!check(charNum, stand)) {break;}ans = Integer.min(ans, r - l);// 左邊向右滑動1位，最左邊位置的字符個數+1charNum[getIndex1234(chars[l])]++;}return ans;}
?/*** QWER 返回下標* @param c* @return*/private static int getIndex1234(char c) {int index = -1;switch (c) {case 'Q':index = 0;break;case 'W':index = 1;break;case 'E':index = 2;break;case 'R':index = 3;break;}return index;}
?private static boolean check(int[] charNum, int stand) {return charNum[0] <= stand && charNum[1] <= stand && charNum[2] <= stand && charNum[3] <= stand;}
}

耗時