Codeforces Round 265 (Div. 1) |
---|
Закончено |
Паша ненавидит палиндромы. Он считает строку s терпимой, если каждый ее символ — это одна из первых p букв латинского алфавита, и s не содержит ни одной подстроки-палиндрома длины 2 или больше.
Паша нашел терпимую строку s длины n. Помогите ему найти лексикографически следующую терпимую строку той же длины, либо определите, что такой не существует.
В первой строке записано два целых числа, разделенных пробелом: n и p (1 ≤ n ≤ 1000; 1 ≤ p ≤ 26). Во второй строке записана строка s, состоящая из n строчных латинских букв. Гарантируется, что строка является терпимой (согласно определению выше).
Если лексикографически следующая терпимая строка той же длины существует, выведите ее. В противном случае выведите «NO» (без кавычек).
3 3
cba
NO
3 4
cba
cbd
4 4
abcd
abda
Строка s лексикографически больше (или просто больше) строки t той же длины, если существует число i, такое что s1 = t1, ..., si = ti, si + 1 > ti + 1.
Лексикографически следующая терпимая строка — это лексикографически минимальная терпимая строка, большая данной.
Палиндром — это строка, которая одинаково читается слева направо и справа налево.
Название |
---|