problem3

class Solution {
public:

    int balancedString(string s) {
        //sliding window
        int n = s.length(),cnt = n/4, ans = n;
        unordered_map<char, int> mp, mp2, count;
        for(char c: s){
            mp[c]++; //get count for each char
        }
        bool found = false;
        for(auto& keyVal: mp){
            if(keyVal.second > cnt){
                found = true;
                mp2[keyVal.first] = keyVal.second - cnt; //map2 keeps the excessive amount of char
            }
        }
        if(!found) return 0; //if no excess, return 0
        int start =0;
        //now find the minimum window which has the required number of char
        for(int i=0; i< n; i++){
            char c = s[i];
            count[c]++;
            //increase start here
            while(true){
                int tmp = start;
                while(start < n && !mp2.count(s[start])){ //for characters not inside mp2, just skip
                    count[s[start++]]--;
                }
                while(start < n && mp2.count(s[start]) && count[s[start]] > mp2[s[start]]){
                    count[s[start++]]--;//if char is inside the mp2 and current count greater than mp2 count, skip
                }
                if(tmp == start) break; //if cannot move further, break
            }

            //check if solution found
            bool found = true;
            for(auto& keyValue: mp2){
                if(count[keyValue.first] < keyValue.second){
                    found = false;
                }
            }
            if(found){
                ans = min(ans, i - start +1); //if found a solution, get the minimal
            }
        }
        return ans;
    }
};