Submission #1942266

---

Source Code Expand

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
string s; int K, cnt[300009];
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cin >> s >> K;
	int n = s.size();
	for (int i = 0; i < n; i++) cnt[i + 1] = cnt[i] + (s[i] != 'a');
	if (cnt[n] <= K) cout << string(n - K, 'a') << '\n';
	else {
		int ca = 0;
		for (int i = 0; i <= n && cnt[i] <= K; i++) ca = max(ca, i + K - cnt[i]);
		vector<int> sp;
		for (int i = 0; i <= n && cnt[i] <= K; i++) {
			if (i + K - cnt[i] == ca) sp.push_back(i);
		}
		string ret = "~";
		for (int i : sp) ret = min(ret, s.substr(i));
		cout << string(ca, 'a') + ret << '\n';
	}
	return 0;
}

Submission Info

Judge Result