Submission #1595516

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

int n, k;
string s;

bool check(string t, char c, map<char, int> mp) {
  int diff = 0;
  t += c;
  mp[c]--;
  for (int i = 0; i < t.size(); i++) {
    diff += s[i] != t[i];
  }

  map<char, int> mp2;
  for (int i = t.size(); i < n; i++) {
    mp2[s[i]]++;
  }

  int sum = 0;
  for (char i = 'a'; i < 'z'; i++) {
    sum += max(0, min(mp[i], mp2[i]));
  }
  diff += n - t.size() - sum;
  return diff <= k;
}

int main(void) {
  cin >> n >> k >> s;

  map<char, int> mp;
  for (int i = 0; i < n; i++) {
    mp[s[i]]++;
  }

  string ans = "";
  for (int i = 0; i < n; i++) {
    for (auto& ch : mp) {
      if (ch.second <= 0) continue;
      if (check(ans, ch.first, mp)) {
        ans += ch.first;
        ch.second--;
        break;
      }
    }
  }

  cout << ans << endl;

  return 0;
}

Submission Info

Judge Result