Сжатие строки

Сжатие строки определяется числом подряд идущих блоков одинаковых символов. Например, в строке «aabbbcaaaad» будет пять блоков: {aa, bbb, c, aaaa, d}. Таким образом, не все строки будут хорошо сжиматься, особенно если буквы часто чередуются. Для этого, перед тем как строку сжимать, будем применять к ней некоторую перестановку чисел от 1 до N. Длина строки кратна длине перестановки, поэтому перестановку применяем сначала для символов от 1 до N, потом от N+1 до 2×N и так далее. Применить перестановку к строке – это значит поменять позиции символов в строке на те позиции, которые в перестановке. Например, если N = 5, взята перестановка «3, 1, 4, 2, 5» и строка «abaabfdzdd», то получим строку «aaabbzfddd». Таким образом, если сжимать строку сразу, то получим восемь блоков {a, b, aa, b, f, d, z, dd}, а если после перестановки, то будет пять блоков {aaa, bb, z, f, ddd}. Как мы видим, размер сжатой строки зависит от выбранной перестановки.

Ваша задача максимально сжать строку, то есть определить минимально возможное число блоков.

Входные данные

Входной файл INPUT.TXT содержит в первой строке натуральное число N (2 ≤ N ≤ 16). Во второй строке содержится строка, состоящая из строчных букв английского алфавита. Длина строки не превышает 10⁶.

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Примеры

Автор задачи

Владимир Игоревич Лукьянчиков

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]