Cycle String?
시간 제한1초메모리 제한256 MB
길이가 짝수인 순환 문자열에서 길이 n인 부분 문자열이 모두 다르도록, 주어진 문자들을 재배열한 문자열을 복원하거나 불가능하면 NO를 출력한다.
문제
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.
입력
The first line contains one string s of length 2·n (2 ≤ 2·n ≤ 1 000 000) which consists only of the lowercase Latin letters.
출력
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.
힌트
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.