BOJ 1545 - 안티 팰린드롬

BOJ 1545 - 안티 팰린드롬

짝수라면 그냥 검사하고 홀수라면 가장 중앙에 존재하는 알파벳중 아무거나 넣어서 최대 $26$번 반복한다고 하자.

$wlog. 2 \mid N$ 이라 하고 어떤 알파벳의 개수가 $c_i$ 일 때, $c_i > \dfrac{N}{2}$ 라면 정답은 불가능하고 그렇지 않다면 항상 가능하다.

구성하는 방법은 일단 사전순으로 작은 문자부터 넣어가면서 그럼 $\dfrac{N}{2}$는 자유롭게 채우면 되고 뒤에 $\dfrac{N}{2}$개는 대칭되는 쪽이 동일한 문자가 아닐 때 까지 사전순으로 작은 문자부터 최대한 채워넣으면 된다.

void solve() {
   string s;
   cin >> s;
   int n = sz(s);
   vi cnt(26);
   for (char c: s) cnt[c - 'a']++;

   vs ans;
   auto cnt_copy = cnt;
   auto chk = [&](string mid) -> bool {
      cnt = cnt_copy;
      int half = n / 2;
      string t(half * 2, ' ');
      int can = 1;
      for (int i = 0; i < 26; i++) {
         if (cnt[i] > half) {
            can = 0;
            break;
         }
      }
      if (!can) return false;

      for (int i = 0; i < half * 2; i++) {
         if (i < half) {
            for (int j = 0; j < 26; j++) {
               if (cnt[j]) {
                  t[i] = char(j + 'a');
                  cnt[j]--;
                  break;
               }
            }
         } else {
            for (int j = 0; j < 26; j++) {
               if (cnt[j] && t[half * 2 - 1 - i] != j + 'a') {
                  t[i] = char(j + 'a');
                  cnt[j]--;
                  break;
               }
            }
         }
      }
      if (sz(mid)) t = t.substr(0, half) + mid + t.substr(half);
      ans.pb(t);
      return true;
   };

   if (n % 2) {
      for (int i = 0; i < 26; i++) {
         if (cnt_copy[i]) {
            cnt_copy[i]--;
            chk(string(1, char(i + 'a')));
            cnt_copy[i]++;
         }
      }
   } else chk("");
   sort(all(ans));
   if (!sz(ans)) cout << -1;
   else cout << ans[0];
}