Олимпиадный тренинг

Задача . D. Раскраска палиндромов


Задача

Темы: Бинарный поиск жадные алгоритмы сортировки Строки *1400

У вас есть строка \(s\), состоящая из строчных букв латинского алфавита.

Вы можете покрасить некоторые буквы в цвета от \(1\) до \(k\). Необязательно красить все буквы. Для каждого цвета должна быть буква, покрашенная в этот цвет.

Затем вы можете сколько угодно раз менять местами любые два символа, покрашенные в один цвет.

После этого будет создано \(k\) строк, \(i\)-я из них будет содержать все символы, покрашенные в цвет \(i\), записанные в порядке их следования в строке \(s\).

Ваша задача покрасить символы строки так, чтобы все полученные \(k\) строк были палиндромами, а длина самой короткой из этих \(k\) строк была как можно больше.

Прочтите пояснение к первому набору входных данных примера, если вам требуется пояснение к условию задачи.

Напомним, что строка является палиндромом, если она читается одинаково как слева направо, так и справа налево. Например, строки abacaba, cccc, z и dxd являются палиндромами, а строки abab и aaabaa — нет.

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

Первая строка входных данных содержит единственное целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных в тесте.

Далее следуют описания наборов входных данных.

Первая строка описания каждого набора входных данных содержит два целых числа \(n\) и \(k\) (\(1 \le k \le n \le 2 \cdot 10^5\)) — длина строки и число цветов, в которые можно красить её буквы. Вторая строка описания каждого набора входных данных содержит строку \(s\) длины \(n\), состоящую из строчных букв латинского алфавита.

Гарантируется, что сумма длин всех строк в тесте не превосходит \(2 \cdot 10^5\).

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

Для каждого набора входных данных выведите единственное целое число — максимальную длину самой короткой строки-палиндрома, которую возможно получить.

Примечание
  • В первом наборе входных данных \(s\)=«bxyaxzay», \(k=2\). Далее будем использовать индексы в строке от \(1\) до \(8\). Подойдет следующая раскраска: \(\mathtt{\mathbf{\color{red}{b}\color{blue}{xy}\color{red}{a}\color{blue}{x}z\color{red}{a}\color{blue}{y}}}\) (буква z осталась непокрашенной). После покраски:
    • поменяем местами два красных символа (с индексами \(1\) и \(4\)) местами, получим \(\mathtt{\mathbf{\color{red}{a}\color{blue}{xy}\color{red}{b}\color{blue}{x}z\color{red}{a}\color{blue}{y}}}\);
    • поменяем местами два синих символа (с индексами \(5\) и \(8\)) местами, получим \(\mathtt{\mathbf{\color{red}{a}\color{blue}{xy}\color{red}{b}\color{blue}{y}z\color{red}{a}\color{blue}{x}}}\).

    Теперь, если для каждого из двух цветов выписать соответствующие буквы слева направо, то получим две строки \(\mathtt{\mathbf{\color{red}{aba}}}\) и \(\mathtt{\mathbf{\color{blue}{xyyx}}}\). Обе они являются палиндромами, длина наименьшей равна \(3\). Можно показать, что большую длину наименее длинного палиндрома достичь нельзя.

  • Во втором наборе входных данных подойдёт такая раскраска: \([1, 1, 2, 2, 3, 3]\). Менять символы местами не нужно. Обе полученные строки равны aa, они являются палиндромами и их длина равна \(2\).
  • В третьем наборе входных данных можно покрасить любой символ и взять его в строку.
  • В четвёртом наборе входных данных можно покрасить \(i\)-й символ в цвет \(i\).
  • В пятом наборе входных данных можно покрасить в каждый из цветов по одному символу.
  • В шестом наборе входных данных подойдёт такая раскраска: \([1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 0]\). Переставим символы так, чтобы получить палиндромы abcba и acbca.

Примеры
№Входные данныеВыходные данные
1 10
8 2
bxyaxzay
6 3
aaaaaa
6 1
abcdef
6 6
abcdef
3 2
dxd
11 2
abcabcabcac
6 6
sipkic
7 2
eatoohd
3 1
llw
6 2
bfvfbv 
3
2
1
1
1
5
1
1
3
3

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


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

Загруженные файлы
Нет