Submission #1215232

---

Source Code Expand

#include "bits/stdc++.h"

using namespace std;
#ifndef _DEBUG
#define main_ main
#endif
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)

template <typename T>
using keyVal = pair<string, T>;
template<typename T>
bool val_greater(const keyVal<T>& left, const keyVal<T>& right) {
	return left.second > right.second;
}


int main_() {
	int N, K;
	cin >> N >> K;
	string S;
	cin >> S;

	// histgram
	map<char, int> hs;
	for (char c = 'a'; c <= 'z'; c++) {
		hs[c] = 0;
	}
	for (char c : S) {
		hs[c]++;
	}

	string t = "";
	map<char, int> ht(hs);

	string asc = S;
	sort(asc.begin(), asc.end());

	int changeable = K;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < asc.size(); j++) {
			// attempt asc[j] at "i"
			hs[S[i]]--;
			ht[asc[j]]--;

			int cg = (S[i] == asc[j]) ? changeable : changeable - 1;

			int unusedCharNum = 0;
			for (char c = 'a'; c <= 'z'; c++) {
				unusedCharNum += min(hs[c], ht[c]);
			}

			int unfixedLen = N - 1 - i;

			// accept asc[j]
			if (unfixedLen - unusedCharNum <= cg) {
				t += asc[j];
				asc.erase(j,1);
				changeable = cg;
				break;
			}

			// reject asc[j] and undo
			hs[S[i]]++;
			ht[asc[j]]++;
		}
	}

	cout << t << endl;

	return 0;
}

Submission Info

Judge Result