Задана строка \(s\) длины \(n\). Каждый символ — это либо одна из первых \(k\) строчных латинских букв, либо знак вопроса.
Требуется заменить каждый знак вопрос на одну из первых \(k\) строчных латинских букв таким образом, чтобы максимизировать следующее значение.
Пусть \(f_i\) будет максимальной длиной подстроки строки \(s\), которая состоит целиком из \(i\)-й латинской буквы. Подстрока строки — это некоторый ее непрерывный подотрезок. Если \(i\)-я буква не встречается в строке, то \(f_i\) равно \(0\).
Значение строки \(s\) — это минимальное значение среди \(f_i\) для всех \(i\) от \(1\) до \(k\).
Какое наибольшее значение может иметь строка?
Выходные данные
Выведите одно целое число — наибольшее значение, которое может иметь строка, если заменить каждый знак вопроса на одну из первых \(k\) строчных латинских букв.
Примечание
В первом примере знаки вопроса можно заменить следующим образом: «aaaababbbb». \(f_1 = 4\), \(f_2 = 4\), поэтому ответ равен \(4\). Можно заменить и таким образом: «aaaabbbbbb». Тогда \(f_1 = 4\), \(f_2 = 6\), однако, минимум из них все еще равен \(4\).
Во втором примере одна из возможных строк такая: «aabbccdda».
В третьем примере хотя бы одна буква не встретится в строке, поэтому минимум из значений \(f_i\) всегда равен \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 2
a??ab????b
|
4
|
|
2
|
9 4
?????????
|
2
|
|
3
|
2 3
??
|
0
|
|
4
|
15 3
??b?babbc??b?aa
|
3
|
|
5
|
4 4
cabd
|
1
|