Perfect Keyboard
Perfect Keyboard
题目来源：codeforces:Educational Codeforces Round 82 (Rated for Div. 2) C题
Polycarp wants to assemble his own keyboard. Layouts with multiple rows are too complicated for him — his keyboard will consist of only one row, where all 26 lowercase Latin letters will be arranged in some order.
Polycarp uses the same password s on all websites where he is registered (it is bad, but he doesn’t care). He wants to assemble a keyboard that will allow to type this password very easily. He doesn’t like to move his fingers while typing the password, so, for each pair of adjacent characters in s, they should be adjacent on the keyboard. For example, if the password is abacaba, then the layout cabdefghi… is perfect, since characters a and c are adjacent on the keyboard, and a and b are adjacent on the keyboard. It is guaranteed that there are no two adjacent equal characters in s, so, for example, the password cannot be password (two characters s are adjacent).
Can you help Polycarp with choosing the perfect layout of the keyboard, if it is possible?
Input
The first line contains one integer T (1≤T≤1000) — the number of test cases.
Then T lines follow, each containing one string s (1≤|s|≤200) representing the test case. s consists of lowercase Latin letters only. There are no two adjacent equal characters in s.
Output
For each test case, do the following:
if it is impossible to assemble a perfect keyboard, print NO (in upper case, it matters in this problem);
otherwise, print YES (in upper case), and then a string consisting of 26 lowercase Latin letters — the perfect layout. Each Latin letter should appear in this string exactly once. If there are multiple answers, print any of them.
Example
input
5
ababa
codedoca
abcda
zxzytyz
abcdefghijklmnopqrstuvwxyza
output
YES
bacdefghijklmnopqrstuvwxyz
YES
edocabfghijklmnpqrstuvwxyz
NO
YES
xzytabcdefghijklmnopqrsuvw
NO
题目大意：给一个字符串，这个字符串全是小写英文字母，并且相邻字符不相同，问是否能设计出一个“完美键盘”（只有一行，26个字母），使得在该“完美键盘”上敲击该字符串时，下一个字母总在当前字母的相邻位置。若存在，输出“YES”及该键盘布局；若不存在，输出“NO”。
提示：样例三很有警示意义，一开始我想的是“每个字母出现频率不高于2，且至少有两个字母出现频率为1即为YES”，但样例三使我“幡然醒悟”。
解题思路：建立一个足够大的数组（大于2*26即可），中间位置放入字符串的第一个字符，并对该位置进行flag标记（相当于指向该位置）,并对该字符进行map映射，表示该字符在此位置，然后遍历字符串，可能出现以下几种情况：
1.该字符从未出现：两种解决方案：（1）flag所指位置的右边为空，将该字符放到flag+1的地方，flag++；（2）flag所指位置的左边为空，将该字符放到flag-1的地方,flag–。
2.该字符出现过，并且其位置就在flag标记的左/右边，则将flag标记左/右移即可。
3.该字符就在flag所标记的位置（由于临近不相等，该情况不可能出现，故省略）。
4.该字符出现过，并且其位置不在flag标记的左/右边，直接标记结束，打印“NO”。
遍历结束后，如果可能出现（结束标记未被标记），则遍历那个“足够大的数组”，从左到右打印“非空位”，然后遍历26个字母，没被打印上的就接着打印，结束。
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
map<int,int>mapp;//该字母的出现位置，初始化均为0
map<char,int>k;//该字母是否被打印过
int main()
{
int t;
cin>>t;
while(t--)
{
string str;
cin>>str;
int num[200];//足够大的数组
memset(num,0,sizeof(num));
int len=str.size();
int cnt[len];//个人习惯，将小写字母转换为数字处理
for(int i=0; i<len; i++)
{
cnt[i]=str[i]-'a'+1;
mapp[cnt[i]]=0;
}
int flag=100;//“光标”标记
num[100]=cnt[0];
mapp[cnt[0]]=100;
int v=0;
for(int i=1; i<len; i++)
{
if(mapp[cnt[i]]==0)//该字母没出现过
{
if(num[flag+1]==0)
{
flag++;
num[flag]=cnt[i];
mapp[cnt[i]]=flag;
}
else if(num[flag-1]==0)
{
flag--;
num[flag]=cnt[i];
mapp[cnt[i]]=flag;
}
else
{
v=1;
break;
}
}
else if(mapp[cnt[i]]==flag-1)//出现过且在光标左边
{
flag--;
}
else if(mapp[cnt[i]]==flag+1)//出现过且在光标右边
{
flag++;
}
else//由于临近不相等，剩下的情况一定是“NO”了
{
v=1;//结束标记
break;
}
}
if(v==0)
{
cout<<"YES"<<endl;
for(int i=0;i<26;i++)
{
k['a'+i]=0;
}
for(int i=0;i<200;i++)//先打印出现过的字母，或是先打印没出现过的字母都可以
{
if(num[i])
{
char c='a'+num[i]-1;
cout<<c;
k[c]=1;
}
}
for(int i=0;i<26;i++)
{
if(k['a'+i]==0)
{
char c='a'+i;
cout<<c;
}
}
cout<<endl;
}
else
cout<<"NO"<<endl;
}
return 0;
}