SRM563 Div1 Easy

300

class FoxAndHandle {
public:
  string lexSmallestName(string S)
  {
    string H;

    const int N = S.size();
    bool vis[N];
    fill(vis, vis + N, false);

    vector< pair<char, int> > cand;
    for (int i = 0; i < N; ++i) {
      cand.push_back(make_pair(S[i], i));
    }
    sort(cand.begin(), cand.end());

    int prev = -1;
    while (H.size() < S.size() / 2) {
      for (int i = 0; i < cand.size(); ++i) {
        int j = cand[i].second;
        unless (prev < j) continue;
        map<char, int> cnt;
        for (int k = 0; k < N; ++k) {
          ++cnt[S[k]];
        }
        for (int k = 0; k < H.size(); ++k) {
          --cnt[H[k]];
          --cnt[H[k]];
        }
        if (cnt[cand[i].first] <= 0) continue;

        int rest = 0;
        for (int k = j; k < N; ++k) {
          if (2 <= cnt[S[k]]) {
            ++rest;
            cnt[S[k]] -= 2;
          }
        }
        if (S.size() / 2 <= H.size() + rest) {
          prev = j;
          H += S[j];
          vis[j] = true;
          break;
        }
      }
    }

    return H;
  }
};