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

﹏ヽ暗。殇╰゛Y 2023-07-05 08:00 6阅读 0赞

**Discription**  
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

**题意**  
给定一个字符串时一串密码，要求对a到z重新排序，使其满足字符串中的相邻关系，若能则输出YES和任意一个排序结果，若不能则输出NO。

**思路**  
遍历一遍。  
对于没有访问过的，标记为访问过了，并且将其插在答案串适当的位置，pos指向新插入的位置；如果pos不是size-1或者0则不符合情况。如果访问过了，则判断pos左右的字符是否是当前字符，如果存在当前字符，则移动到当前字符所在位置；若不存在，则不符合情况。

**AC代码**

#include <bits/stdc++.h>
    typedef long long ll;
    using namespace std;
    
    int a[100];
    int T,flag;
    string s,ans;
    
    int main()
    { 
        cin >> T;
        while(T--)
        { 
            ans = "";
            cin>>s;
            flag=0;
            for (int i=0; i<26; ++i)
                a[i]=0;
            int len=s.size(), pos=0;
            for (int i=0; i<len; ++i)
            { 
                if (a[s[i]-'a'])
                { 
                    if (pos<(int)ans.size()-1&&ans[pos+1]==s[i])
                        ++pos;
                    else if(pos&&ans[pos-1]==s[i])
                        --pos;
                    else
                    { 
                        flag=1;
                        break;
                    }
                }
                else
                { 
                    a[s[i] - 'a'] = 1;
                    if (pos == ans.size() - 1)
                    { 
                        ans += s[i];
                        ++pos;
                    }
                    else if (pos == 0)
                        ans = s[i] + ans;
                    else
                    { 
                        flag=1;
                        break;
                    }
                }
            }
            if(flag==1)
            { 
                cout<<"NO"<<endl;
                continue;
            }
            cout<<"YES"<<endl;
            cout<<ans;
            for(int i=0; i<26; ++i)
                if(!a[i])
                    cout<<(char)(i+'a');
            cout<<endl;
        }
        return 0;
    }