Submission #1304952

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define first  fs
#define second se
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; ++i)

using pii = pair<int, int>;
using vi = vector<int>;
using lint = long long;

const int inf = 1001001001;
const lint linf = 1001001001001001001ll;
const int mod = 1e9 + 7;
const int dx[]{0, 1, 0, -1, -1, -1, 1, 1}, dy[]{1, 0, -1, 0, -1, 1, -1, 1};

template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; } return a > b; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; } return a < b; }
template<typename T> inline void print(const T &x, char s = '\n') { cout << x << s; }
template<typename T> inline void print(const vector<T> &v, string s = " ") 
{ rep(i, v.size()) cout << v[i] << (i + 1 == v.size() ? "\n" : s); }
inline bool inside(int y, int x, int H, int W) { return 0 <= y && y < H && 0 <= x && x < W; }
inline lint in() { lint x; std::cin>>x; return x; }

bool check(string& s, string& t, int k) {
	vi a(26);
	
	rep(i, s.size()) {
		a[s[i] - 'a']++;
	}

	rep(i, s.size()) {
		if (t[i] == '?') {
			int j = s[i] - 'a';
			if (a[j] > 0) a[j]--;
			else k--;
		} 
		else {
			int j = t[i] - 'a';
			if (a[j] > 0) a[j]--;
			else return false;

			if (s[i] != t[i]) k--;
		}
	}

	return k >= 0;
}

int main() {
	int n, k;
	string s, t;

	cin >> n >> k >> s;
	t = string(n, '?');

	for (int i = 0; i < n; ++i) {
		for (char c = 'a'; ; ++c) {
			t[i] = c;
			if (check(s, t, k)) break;
		}
	}

	print(t);
}

Submission Info

Judge Result