Description

Submission

class Solution {
    int presum[100005][4];
    int freq[4];
public:
    int balancedString(string s) {
        int n = s.length();
        map<char, int> c2i {{'Q', 0}, {'W', 1}, {'E', 2}, {'R', 3}};
        
        for(char c: s) {
            freq[c2i[c]]++;
        }
        
        int target = n / 4;
        vector<int> diff(4);
        
        for(int i = 0; i < 4; ++i) {
            diff[i] = max(freq[i] - target, 0);
        }
        
        s.insert(s.begin(), ' ');
        for(int i = 1; i < n + 1; ++i) {
            for(int j = 0; j < 4; ++j) {
                presum[i][j] = presum[i-1][j];
            }
            presum[i][c2i[s[i]]]++;
        }
        
        int ret = INT_MAX;
        int i = 0, j = 0;
        set<int> exist;
        for(int i = 0; i < 4; ++i) {
            if(diff[i]) exist.insert(i);
        }
        
        while(i < n+1 && j < n+1) {
            for(; i < j && exist.find(c2i[s[i+1]]) == exist.end(); i++);
            
            bool noLess = true;
            for(int k = 0; k < 4; ++k) {
                if(!diff[k]) continue;
                int d = presum[j][k] - presum[i][k];
                if(d < diff[k]) {
                    noLess = false;
                }
            }       
            
            if(i > j) j = i;

            if(noLess) {
                ret = min(j - i, ret);
                i++;
            } else {
                j++;
            }
        }
        
        return ret;
    }
};