【Leetcode Daily】1234替换子串得到平衡字符串

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，给一个由 QWER 四个字母组成的字符串，可以变换其中的子字符串，使得四个字母数量相同，求变换的子字符串的最短长度。

思路分享

• 不定长滑动窗口的求“至少”应用，思路上基本同【Leetcode Daily】3090每个字符最多出现两次的最长字符串，下面主要讲讲灵茶山艾府在题解中可以借鉴的地方。

  https://leetcode.cn/problems/replace-the-substring-for-balanced-string/solutions/2108358/tong-xiang-shuang-zhi-zhen-hua-dong-chua-z7tu/

• 一个是数组的初始化，由于 ASCII 码的对应，其实用字符初始化数组数量是可以的，所以就有了int rec['Z']{}这种写法。

• 另一个是结果在窗口合法时更新，避免窗口不合法后，去猜合法情况的代码。这样做很容易把自己绕进去。

代码解答（强烈建议自行解答后再看）

• 参考解法

class Solution {
public:
    int balancedString(string s) {
        int n = s.size();
        int rec['X']{};
        for (const char &c:s) {
            rec[c]++;
        }
        int base = n/4;

        
        // rec的意思变为窗口内多余的字母
        if (rec['Q']==base && rec['W']==base && rec['E']==base && rec['R']==base) return 0;
        int ans = INT_MAX;

        int left = 0;
        for (int right=0; right < n; right++) {
            rec[s[right]]--;
            
            while(rec['Q']<=base && rec['W']<=base && rec['E']<=base && rec['R']<=base) {
                ans = min(ans, right-left+1);
                // cout << left << " " << right << " " << rec['Q'] << rec['W'] << rec['E']<<rec['R'] << endl;
                rec[s[left++]]++;
            }
            //cout << left << " " << right << " " << rec['Q'] << rec['W'] << rec['E']<<rec['R'] << endl;
            
        }
        return ans;
    }
};