Link: Cycle String?

Cycle String?

Description:
Great wizard gave Alice and Bob a cycle string of length 2⋅n, which has no repeated substrings of length n. In a cycle string, character si+1 comes after si. Also, s1 comes after s2n.

Unfortunately, evil gin shuffled all the symbols of the string. Help Alice and Bob restore the original string so that the above condition is satisfied.

Input
The first line contains one string s of length 2⋅n (2≤2⋅n≤1000000) which consists only of the lowercase Latin letters.

Output
Print "NO" (without quotes) to the first line if it is impossible to restore the string so that the condition is satisfied. Otherwise, in the first line print "YES" (without quotes).

In the second line print one string — the restored string.

If there are multiple answers, print any.

Examples
Input
cbbabcacbb
Output
YES
abbabcbccb
Input
aa
Output
NO
Input
afedbc
Output
YES
afedbc
Note
In the first example, substrings of the restored string are: "abbab", "bbabc", "babcb", "abcbc", "bcbcc", "cbccb", "bccba", "ccbab", "cbabb", "babba".

Note that the first example does not contain repetitions, however it can be rewritten as another cycle with no repetitions. Thus, the solution is not unique — the given example is also a correct solution.

In the second example, it is impossible to restore the string so that no repetition exists.

In the third example, there is no need to change anything.

Problem solving:
这道题的意思就是给你一个长度为2n的字符串，问你它所有的长度为n的字串有没有重复的。如果有重复的，看能不能通过交换某几个字母的位置来避免相同子串的产生，如果可以就输出"YES"，否则输出"NO"。交换次数是无限次的。

因为交换次数是无限的的，所以我们只考虑每种字母的个数就行了。我们首先可以用一个数组存一下每个字符出现的次数。通过我跟我队友找规律发现，只要有某个字母出现的次数大于n并且只出现了两种以内的字母，并且出现次数少的那个字母只出现过一次时输出NO。否则就肯定可以。

然后输出转换后的序列的时候需要先排一个序，然后从个数多的存进一个字符串，但是这个时候可能会出现某种情况导致会有重复的字串出现，所以我们需要来一个小处理即swap(ans[l-2],ans[l/2]);就是把第n+1位的字符与第n-1位的字符交换一下。

Code:

#include <bits/stdc++.h>
using namespace std;
int a[30];
struct node
{
    char c; int v;
} p[30];
bool cmp(node a, node b)
{
    return a.v > b.v;
}
int main()
{
    set<char> se;
    string    s, ans;
    cin >> s;
    int       l = s.size();
    for (int i = 0; i < s.size(); i++)
        a[s[i] - 'a']++, se.insert(s[i]);
    int mid = se.size();
    for (int i = 0; i < 26; i++)
    {
        if (a[i] > l / 2 && mid <= 2)
            if (!(a[i] < l - 2))
                return cout << "NO\n", 0;
    }
    cout << "YES\n";
    for (int i = 0; i < 26; i++)
    {
        p[i].c = i + 'a';
        p[i].v = a[i];
    }
    sort(p, p + 26, cmp);
    for (int i = 0; i < 26; i++)
    {
        while (p[i].v--)
            ans += p[i].c;
    }
    swap(ans[l-2],ans[l/2]);
    cout << ans << endl;
    return 0;
}
赏