【題目敘述】http://codeforces.com/contest/1303/problem/C
- set <int> st[26]; 紀錄每個字母的相鄰字母。（去除重複）
- bool f(int x); 判斷擺放第x個字母後，後續會不會有不合法的情況。
- (Line-37)：當一個字母有兩個以上相鄰的字母時，無解。
- (Line-47)：當一個字母只有一個相鄰字母時，直接擺放它，並由此開始往其相鄰字母進行檢查。
- (Line-55)：如果最後還剩下有相鄰字母的要求卻未能成功安置的字母，無解。
- (Line-64)：最後記得把所有還沒用過的字母都加進去。
#include <iostream>
#include <vector>
#include <set>
#include <cstring>
using namespace std;
int t, used[26], cnt;
string s;
set <int> st[26];
vector <int> ans;
bool flag;
bool f(int x){
if (used[x] == 1) return 0;
used[x] = 1;
ans.push_back(x);
if (st[x].size() == 0) return 1;
int nxt = *(st[x].begin());
st[nxt].erase(x);
st[x].erase(nxt);
return f(nxt);
}
int main() {
cin >> t;
while (t--){
cin >> s;
for (int i = 0; i < 26; i++){
st[i].clear();
}
for (int i = 1; i < s.length(); i++){
st[s[i]-'a'].insert(s[i-1]-'a');
st[s[i-1]-'a'].insert(s[i]-'a');
}
flag = true;
for (int i = 0; i < 26; i++){
if (st[i].size() > 2){
cout << "NO\n";
flag = false;
break;
}
}
if (!flag) continue;
memset(used, 0, sizeof(used));
ans.clear();
for (int i = 0; i < 26; i++){
if (st[i].size() == 1 && !f(i)){
cout << "NO\n";
flag = false;
break;
}
}
if (!flag) continue;
for (int i = 0; i < 26; i++){
if (st[i].size()){
cout << "NO\n";
flag = false;
break;
}
}
if (!flag) continue;
cout << "YES\n";
for (int i = 0; i < 26; i++){
if (used[i] == 0) ans.push_back(i);
}
for (int i = 0; i < 26; i++){
cout << (char)('a'+ans[i]);
}
cout << "\n";
}
}