Циклическая строка?
Циклическая строка?
Великий волшебник дал Алисе и Бобу циклическую строку длины 2 * n, в которой нет повторяющихся подстрок длины n. В строке цикла символ si+1
идет после si
. Кроме того, s1
идет после s2n
.
К сожалению, злой джин перетасовал все символы строки. Помогите Алисе и Бобу восстановить исходную строку так, чтобы выполнялось вышеуказанное условие.
Входные данные
Содержит одну строку s длины 2 * n (2 ≤ 2 * n ≤ 106
), состоящую только из строчных латинских букв.
Выходные данные
Выведите "NO" в первой строке, если невозможно восстановить строку так, чтобы выполнялось условие. В противном случае в первой строке выведите "YES".
Во второй строке выведите восстановленную строку. Если ответов несколько, выведите любой.
Пояснение
В первом примере подстроками восстановленной строки являются: “abbab”, “bbabc”, “babcb”, “abcbc”, “bcbcc”, “cbccb”, “bccba”, “ccbab”, “cbabb”, “babba”.
Обратите внимание, что первый пример не содержит повторений, однако его можно переписать как еще один цикл без повторов. Таким образом, решение не единственное - данный пример также является правильным решением.
Во втором примере невозможно восстановить строку так, чтобы не было повторений.
В третьем примере ничего менять не нужно.
cbbabcacbb
YES aabbbcccbb
aa
NO
afedbc
YES abcfde