Ctrl K

Наибольшая строка без длинных повторов

Средняя
Дан набор букв — строка letters — и число max_run. Составьте из этих букв новую строку, в которой ни одна буква не повторяется больше max_run раз подряд. Использовать все буквы не обязательно, но каждую букву из letters можно взять не больше одного раза. Верните лексикографически наибольшую такую строку. Строка a больше строки b, если в первой позиции, где они различаются, у a буква дальше по алфавиту; если же одна строка — начало другой, больше та, что длиннее.
Пример 1
letters="yxyyy", max_run=2 → 'yyxyy'

Хочется поставить все четыре y подряд, но больше двух нельзя. Получаем yy, затем разделитель x, затем оставшиеся yy: «yyxyy».

Пример 2
letters="cccca", max_run=1 → 'cac'

После каждой c нужен разделитель, а он только один — a. Получается «cac», остальные c использовать нельзя.

Пример 3
letters="bab", max_run=3 → 'bba'
Ограничения
  • 1 ≤ max_run ≤ len(letters) ≤ 10⁵
  • letters состоит из строчных латинских букв
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиБез одинаковых соседей СредняяЗаполнить пропуски с минимумом повторов СредняяОдинаковые буквы на расстоянии СложнаяСимволы, сгруппированные по частоте СредняяЗадания с перерывом на остывание Средняя
загружаем Python…
Вход
letters="yxyyy", max_run=2
Ожидается
'yyxyy'

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