回文は，外から決めるか内から決めるかのどちらかが基本． 今回は外から決めることにするが，どちらでも可能．
- \(a_{i}\) と \(a_{n-1-i}\) に共通の文字があればそれを使う，
- なければ回文が作れない
これを \(i\) について貪欲に決めていく． 今までの決め方に依存しないで決まるのがポイント． およそ \(i \in N/2\) までで良く， \(N\) が偶数と奇数で場合分けする．
実装
\(a_{i}\) と \(a_{n-1-i}\) の共通の文字を求めるとき， bit 演算が便利． \(a_{i}\) に現れる文字を整数型に記録する． 現れるか否かが重要であって，何個現れるかは重要でない．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m, k, q;
cin >> n;
cinv(s);
vll v(n);
rep(i,n){
rep(j,n){
char c = s[i][j];
c -= 'a';
v[i] |= (1LL << c);
}
}
string ans;
rep(i,n/2){
ll j = n - i -1;
ll x = v[i] & v[j];
if(x == 0){
cout << -1 << endl;
return 0;
}
rep(c,26) if(x >> c & 1){
ans.push_back(char(c+'a'));
break;
}
}
string rev = ans;
reverse(all(rev)); // do not forget
if(n % 2 == 1){
rep(c,26){
if(v[n/2] >> c & 1){
ans.push_back(char(c+'a'));
break;
}
}
}
ans = ans + rev;
cout << ans << endl;
return 0;
}
