1234. 替換子字串得到平衡字串

推薦事前閱讀：滑動窗口

思路

程式碼

滑動窗口

class Solution {
private:
    int getID(char ch) {
        if(ch == 'Q') return 0;
        else if(ch == 'W') return 1;
        else if(ch == 'E') return 2;
        else if(ch == 'R') return 3;
        return -1;
    }
public:
    int balancedString(string s) {
        int n = s.length();

        // 1. 統計字元出現次數
        int cnt[4]{};        
        for(int i = 0; i < n; ++i) {
            cnt[getID(s[i])]++;
        }
        
        // 2. 債務表更新
        int m = n / 4;
        int debt = 0;
        for(int i = 0; i < 4; i++) {
            cnt[i] = min(0, m - cnt[i]); // 如果比 m 多, 相減是負數, 代表欠，比 m 少會是 0, 代表沒欠
            debt -= cnt[i]; // 如果有欠債, cnt[i] 是負數, 所以用減的
        }
        if(debt == 0) return 0; // 沒有債務，不需要修改字串

        // 3. 找到最短字串
        int res = n;
        for(int i = 0, j = 0; j < n; j++) {
            if(cnt[getID(s[j])]++ < 0) { // 還債 
                debt--; // 還的字元的確是需要的
            }
            if(debt == 0) {
                while(cnt[getID(s[i])] > 0) { // 左邊界的字元有盈餘
                    cnt[getID(s[i++])]--; // 移動左邊界
                }
                res = min(res, j - i + 1);
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$