Ctrl K

Следующая строка без палиндромов

Сложная
Назовём строку **аккуратной**, если она составлена только из первых letters букв латинского алфавита и в ней нет ни одного палиндрома длиной 2 и больше, записанного подряд (то есть никакие две соседние буквы не совпадают и никакие две буквы через одну тоже). Дана аккуратная строка word. Найдите лексикографически наименьшую аккуратную строку той же длины, которая строго больше word. Если такой нет, верните пустую строку. Из двух строк одной длины больше та, у которой в первой различающейся позиции стоит буква дальше по алфавиту.
Пример 1
word="abcd", letters=4 → 'abda'

Последнюю d поднять некуда. Третью букву c можно заменить на d: она не совпадает ни с b, ни с a перед ней. Последнюю позицию заполняем самой маленькой подходящей буквой — a. Получаем abda.

Пример 2
word="dcb", letters=4 → ''

Последнюю b можно поднять только до c или d, но обе уже стоят рядом. Вторую c — только до d, а это соседняя буква. Первая d уже максимальная. Ответа нет — пустая строка.

Пример 3
word="bad", letters=6 → 'bae'

Достаточно заменить последнюю d на e.

Ограничения
  • 1 ≤ len(word) ≤ 10⁵
  • 4 ≤ letters ≤ 26
  • word — аккуратная строка
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиПодходит ли строка под шаблон СложнаяОдинаковые буквы на расстоянии СложнаяДовести пароль до надёжного СложнаяРазличимые сокращения слов СложнаяЗеркальная нарезка строки Сложная
загружаем Python…
Вход
word="abcd", letters=4
Ожидается
'abda'

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 44 теста на сервере, включая скрытые.