Задана строка \(s\) длины \(n\) и целое число \(k\) (\(1 \le k \le n\)). Скажем, что строка \(s\) имеет уровень \(x\), если \(x\) это наибольшее неотрицательное целое число, такое что в строке \(s\) можно выбрать:
Подстрока — это последовательность подряд идущих символов строки, подстрока определяется парой целых чисел \(i\) и \(j\) (\(1 \le i \le j \le n\)), обозначается как \(s[i \dots j]\) = «\(s_{i}s_{i+1} \dots s_{j}\)».
Например, если \(k = 2\), то:
Зухаир дал вам целое число \(k\) и строку \(s\) длины \(n\). Вам нужно найти \(x\) — уровень строки \(s\).
Первая строка содержит два целых числа \(n\) и \(k\) (\(1 \le k \le n \le 2 \cdot 10^5\)) — длину строки и значение \(k\).
Вторая строка содержит строку \(s\) длины \(n\), состоящую из строчных латинских букв.
Выведите одно целое число \(x\) — уровень строки.
В первом примере мы можем выбрать \(2\) непересекающиеся строки, состоящей из буквы «a»: «(aa)ac(aa)bb», так что уровень равен \(2\).
Во втором примере мы можем выбрать или подстроку «a» или «b» чтобы получить ответ \(1\).
8 2 aaacaabb
2
2 1 ab
1
4 2 abab
0
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач