SRM551 Div1 Easy

250

並べる文字と並べる位置を全部試す。

class ColorfulChocolates {
public:
  int maximumSpread(string s, int ms)
  {
    map< char, vector<int> > idx;
    for (int i = 0; i < s.size(); ++i) {
      idx[s[i]].push_back(i);
    }

    int ret = 0;
    for (char c = 'A'; c <= 'Z'; ++c) {
      vector<int> v = idx[c];
      for (int i = 0; i < v.size(); ++i) {
        for (int j = 0; j < s.size(); ++j) {
          int cost = 0;
          int cnt = 0;
          for (int k = i; k < v.size(); ++k) {
            cost += abs((j + cnt) - v[k]);
            ++cnt;
            if (cost <= ms) ret = max(ret, cnt);
          }
        }
      }
    }
    return ret;
  }
};