これ楽しい！

問題概要

長さ $N$ の英小文字のみからなる文字列 $S$ が与えられます。 $S$ の文字を入れ替えることによって、次の条件を満たす文字列 $T$ を作ることができるかどうかを判定してください (可能ならば具体例を 1 つ挙げてください)。

$T$ のどの長さ 2 以上の連続する部分文字列も回文ではない。

制約

$1 \le N \le 10^{5}$

必要条件を列挙しながら、条件の言い換え

まず、「長さ 2 以上の連続する部分文字列も回文でない」という条件をわかりやすく言い換えていくことにしよう！！！

そのためには「必要条件を列挙して十分性が成り立つのを待つ」という方針が有効になることが多いイメージ。とりあえず直ちに思い浮かぶのは

同じ文字が連続してはダメ (その 2 文字が回文となるため)
同じ文字が 1 文字分間隔を空けて配置されるのもダメ (その 3 文字が回文となるため)

よって、「どの連続する 3 文字も互いに相異なる」が必要条件として挙げられる。そして逆にこれを満たせば、どの連続する 3 文字も回文ではなくなるので OK。

Greedy へ

以上を踏まえて判定方法を考える。

使用文字が 1 種類のみの場合は、 $N = 1$ に限り OK
使用文字が 2 種類のみの場合は、 $N = 2$ に限り OK

使用文字が 3 種類以上あるときは、直感的には Greedy でよさそう。つまり、

1 個前の文字と 2 個前の文字以外の文字のうち
残り最多の文字を採用していく (そのようなものが存在しなくなったら "-1")

念のための証明としては、次のような感じでできる。

が 3 の倍数のとき、
- 頻度が $N/3$ より大きいものがあったらダメ
- それ以外は上記の Greedy で実際に作れる
が 3 で割って 1 あまるとき
- 頻度が $N/3 + 1$ より大きいものがあったらダメ
- 頻度が $N/3 + 1$ であるものが 2 個以上あったらダメ
- それ以外は上記の Greedy で実際に作れる
が 3 で割って 2 あまるとき
- 頻度が $N/3 + 1$ より大きいものがあったらダメ
- それ以外は上記の Greedy で実際に作れる

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

string solve(int N, const string &S) {
    map<char,int> ma;
    for (auto c : S) ma[c]++;
    if (ma.size() == 1) {
        if (N == 1) return S;
        else return "-1";
    }
    else if (ma.size() == 2) {
        if (N == 2) return S;
        else return "-1";
    }
    else {
        string res = "";
        while (!ma.empty()) {
            int vmax = -1;
            char pmax;
            for (auto it : ma) {
                if (res.size() > 0 && res.back() == it.first) continue;
                if (res.size() > 1 && res[res.size() - 2] == it.first) continue;
                if (chmax(vmax, it.second)) pmax = it.first;
            }
            if (vmax == -1) return "-1";
            res += pmax;
            ma[pmax]--;
            if (ma[pmax] == 0) ma.erase(pmax);
        }
        return res;
    }
}

int main() {
    int N;
    string S;
    cin >> N >> S;
    cout << solve(N, S) << endl;
}