Educational Codeforces Round 82 (Rated for Div. 2) C. Perfect Keyboard

题目链接
题意：给你一个字符串，让你构造一个26字母的排列，使得给定字符串中若相邻的字符在排列中也相邻。不存在输出NO.
思路：首先一个显然的不可能构造出来的情况是，有个字母跟>2个不同字母相邻。
然后再看能不能构造出可行解。
一个暴力点的做法就是枚举排列的第一个字符然后依次构造，构造完成再check一下合法性即可.
因为可行解一定可以由这种方式构造出来:第一个字符显然只能和一个不同的字符相邻，第二个字符最多只能跟一个不同于第一个字符的不同字符相邻…
细节见代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int t,d[33][33],vis[33],b[33][33],ch[33][33];
char a[N];
int check(vector<int>& ta){
  memset(ch,0,sizeof ch);
  for(int i=1;i<ta.size();i++){
    ch[ta[i]][ta[i-1]]=ch[ta[i-1]][ta[i]]=1;
  }
  for(int i=1;i<=26;i++){
    for(int j=1;j<=26;j++){
      if(b[i][j]!=ch[i][j])return 0;
    }
  }
  return 1;
}
int main() {
  ios::sync_with_stdio(false);
  for(cin>>t;t;t--){
    cin>>a+1;
    int n=strlen(a+1);
    memset(d,0,sizeof d);
    memset(b,0,sizeof b);
    memset(vis,1,sizeof vis);
    for(int i=1;i<=n;i++)vis[a[i]-'a'+1]=0;
    for(int i=2;i<=n;i++){
      if(a[i]==a[i-1]) continue;
      d[a[i]-'a'+1][a[i-1]-'a'+1]=d[a[i-1]-'a'+1][a[i]-'a'+1]=1;
      b[a[i]-'a'+1][a[i-1]-'a'+1]=b[a[i-1]-'a'+1][a[i]-'a'+1]=1;
    }
    vector<int>ans;
    for(int i=1;i<=26;i++){
      if(vis[i])ans.pb(i);
    }
    //cout<<ans.size()<<endl;
    int cat=0;
    for(int i=1;i<=26;i++){
      if(!vis[i]){
        vector<int>tmp,res(27,0);
        int fa=i,len=1;
        res[fa]=1;
        tmp.pb(i);
        while(1){
          int ok=0;
          for(int j=1;j<=26;j++){
            if(!vis[j]&&!res[j]){
              if(d[j][fa]){
                tmp.pb(j);
                fa=j;
                res[j]=1;
                ok=1;
                break;
              }
            }
          }
          if(!ok)break;
        }
        if(tmp.size()+ans.size()==26 &&check(tmp)){
          cat=1;
          for(auto x:tmp)ans.pb(x);
          break;
        }
      }
    }
    if(!cat)cout<<"NO\n";
    else{
      cout<<"YES\n";
      for(auto k:ans)cout<<(char)(k-1+'a');
      cout<<'\n';
    }
  }
  return 0;
}