class Solution {
public:

    bool isOk(const map<char,int> &a, const map<char,int> &b) {
        bool ok = true;
        for(auto it: a) {
            auto it2 = b.find(it.first);
            int cnt = it2 == b.end() ? 0 : it2->second;
            ok &= it.first >= cnt;
        }
        return ok;
    }

    int balancedString(string s) {
        map<char,int> mp;
        for(char &ch : s) mp[ch]++;
        printf("%d\n",mp.size());
        int n = s.size();
        for(auto it = mp.begin(); it!=mp.end();) {
            if(it->second <= (n/4)) {
                mp.erase(it++);
            } else {
                it->second -= (n/4);
                it++;
            }
        }
        printf("%d\n",mp.size());
        if(mp.empty()) return 0;
        int L = 0, R = n;
        while(L < R-1) {
            int m = (L+R) / 2;
            printf("%d %d %d\n",L,m,R);
            bool ok = false;
            map<char,int> tmp;
            for(int i=0;i<m;i++) {
                tmp[s[i]]++;
            }
            ok |= isOk(tmp,mp);
            printf("ok: %d\n",ok);
            for(int j=m;j<n && !ok;j++) {
                char ch = s[j-m];
                auto it = tmp.find(ch);
                if(it->second == 1) tmp.erase(it);
                else it->second--;
                tmp[s[j]]++;
                ok |= isOk(tmp,mp);
            }
            if(ok) {
                R = m;
            } else {
                L = m;
            }
        }
        return R;
    }
};