題意#
給定一個由大寫英文字母組成的字串（長度最長可達 \( 10^6 \)）。
將這些字母重新擺放，試著排成一個「迴文」。
如果能夠排成迴文，輸出一種排法；
若無法排成迴文，輸出 NO SOLUTION。
思路#
構成迴文的條件是「對稱」，
因此字串中大部分的字母出現次數必須是偶數，
這樣才能將它們對半分到迴文的左右兩側。
當字串長度為奇數時，允許有「剛好一種」字母的出現次數為奇數。
這組奇數次數的字母會被放在迴文的正中間作為對稱軸。
我們可以使用 Hash Map 統計每種字母的出現次數。
如果發現有超過 1 種字母的數量是奇數，就無法構成迴文，直接輸出 NO SOLUTION。
若檢查皆符合條件，便可開始組裝字串。
將出現偶數次的字母取一半拿去組成前半段字串 t，
若有一組出現奇數次的字母，就將其組成字串 mid。
最後，依序輸出 t、mid，並將 t 反轉後再輸出一次，即可構成迴文。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
string s, t, mid;
int cnt = 0; // cnt 紀錄出現過奇數次的字母種類數
cin >> s; // 讀取初始字串
unordered_map<char, int> mp;
for (auto c : s) mp[c]++; // 統計每種字母的出現總次數
// 抓出出現奇數次的字母，並串聯成置中的對稱軸字串 mid
for (auto i : mp) if (i.se&1) cnt++, mid = string(i.se, i.fi);
// 如果奇數次的字母種類大於 1，代表絕對無法完美對稱，直接判死刑
if (cnt > 1) return cout << "NO SOLUTION", 0;
// 接著把出現偶數次的字母通通砍半，塞進前半段字串 t 裡
for (auto i : mp) if (!(i.se&1)) t += string(i.se/2, i.fi);
// 組裝輸出：前半段 t + 奇數對稱軸 mid + 倒轉過來的後半段 t
cout << t << mid << string(t.rbegin(), t.rend());
}
