Submission #4048277

---

Source Code Expand

#define _GLIBCXX_DEBUG
#define _USE_MATH_DEFINES
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
#include <queue>

typedef long long ll;

void print(){ std::cout << std::endl; }
template <typename Head> void print(Head&& head) { std::cout << head << std::endl; }
template <typename Head, typename... Tail> void print(Head&& head, Tail&&... tail)
{
  std::cout << head << " ";
  print(std::forward<Tail>(tail)...); // or print(tail...);
}
template<typename Iterator> void print(Iterator begin, Iterator end)
{
  for (Iterator it = begin; it != end; it++) {
    std::cout << "[" << std::distance(begin, it) << "] " << *it << " ";
    if (std::distance(begin, it) % 20 == 19) { std::cout << std::endl; }
  }
  std::cout << std::endl;
}

int main(int argc, char* argv[])
{
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int n, k;
  std::string s;
  std::cin >> n >> k >> s;
  std::string t(n, '#');

  std::vector< int > remain(256, 0);
  for (int i=0; i < n; i++) {
    remain[(int)s[i]]++;
  }

  for (int i=0; i < n; i++) {
    for(int c='a'; c <= 'z'; c++) {
      if (remain[c] <= 0) continue;
      std::vector< int > remain_copy = remain;
      t[i] = c;
      remain_copy[c]--;
      for (int j = i+1; j < n; j++) {
	if (remain_copy[(int)s[j]] > 0) {
	  remain_copy[s[j]]--;
	  t[j] = s[j];
	} else {
	  t[j] = '#';
	}
      }
      //print("t:", i, t);
      int cnt = 0;
      for (int j = 0; j < n; j++) {
	if (s[j] != t[j]) cnt++;
      }
      if (cnt <= k) {
	remain[c]--;
	break;
      }
    }
  }

  print(t);
  return 0;
}

Submission Info

Judge Result