Перестановка блоков перед RLE
Задача по программированию с проверкой онлайн
- Сложность
- Сложная
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Динамическое программирование
- Строки
Дано число k и строка text из строчных латинских букв, длина которой кратна k. Строка делится на блоки по k подряд идущих букв. Выберите перестановку p позиций 1..k и примените её к каждому блоку (одну и ту же ко всем): j-й буквой нового блока становится p[j]-я буква старого. Например, перестановка [3, 1, 4, 2] превращает "abcdefgh" в "cadbgehf".
Сжатый размер строки — число максимальных групп подряд идущих одинаковых букв: у "aabcaaaa" он равен 4. Верните наименьший сжатый размер, который можно получить, выбрав перестановку.
Ограничения: 1 ≤ k ≤ 10, длина строки от k до 2000.
Пример: 4, "abcabcabcabc" → 7.
Источник: Coding Competitions Archive, codejam/2008/round_2/permrle · © Google LLC · Apache-2.0 · условие переведено и дополнено