SHARE
TWEET

Untitled

a guest Nov 9th, 2019 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.    
  4.     bool isOk(const map<char,int> &a, const map<char,int> &b) {
  5.         bool ok = true;
  6.         for(auto it: a) {
  7.             auto it2 = b.find(it.first);
  8.             int cnt = it2 == b.end() ? 0 : it2->second;
  9.             ok &= it.first >= cnt;
  10.         }
  11.         return ok;
  12.     }
  13.    
  14.     int balancedString(string s) {
  15.         map<char,int> mp;
  16.         for(char &ch : s) mp[ch]++;
  17.         printf("%d\n",mp.size());
  18.         int n = s.size();
  19.         for(auto it = mp.begin(); it!=mp.end();) {
  20.             if(it->second <= (n/4)) {
  21.                 mp.erase(it++);
  22.             } else {
  23.                 it->second -= (n/4);
  24.                 it++;
  25.             }
  26.         }
  27.         printf("%d\n",mp.size());
  28.         if(mp.empty()) return 0;
  29.         int L = 0, R = n;
  30.         while(L < R-1) {        
  31.             int m = (L+R) / 2;
  32.             printf("%d %d %d\n",L,m,R);
  33.             bool ok = false;
  34.             map<char,int> tmp;
  35.             for(int i=0;i<m;i++) {
  36.                 tmp[s[i]]++;
  37.             }
  38.             ok |= isOk(tmp,mp);
  39.             printf("ok: %d\n",ok);
  40.             for(int j=m;j<n && !ok;j++) {
  41.                 char ch = s[j-m];
  42.                 auto it = tmp.find(ch);
  43.                 if(it->second == 1) tmp.erase(it);
  44.                 else it->second--;
  45.                 tmp[s[j]]++;
  46.                 ok |= isOk(tmp,mp);
  47.             }
  48.             if(ok) {
  49.                 R = m;
  50.             } else {
  51.                 L = m;
  52.             }
  53.         }
  54.         return R;
  55.     }
  56. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top