Задача . B. Зухаир и строки

Задана строка \(s\) длины \(n\) и целое число \(k\) (\(1 \le k \le n\)). Скажем, что строка \(s\) имеет уровень \(x\), если \(x\) это наибольшее неотрицательное целое число, такое что в строке \(s\) можно выбрать:

• \(x\) непересекающихся подстрок длины \(k\),
• все символы в этих \(x\) подстроках должны быть одинаковы (т.е. каждая подстрока содержит только один различный символ, который один и тот же для всех выбранных подстрок).

Подстрока — это последовательность подряд идущих символов строки, подстрока определяется парой целых чисел \(i\) и \(j\) (\(1 \le i \le j \le n\)), обозначается как \(s[i \dots j]\) = «\(s_{i}s_{i+1} \dots s_{j}\)».

Например, если \(k = 2\), то:

• строка «aabb» имеет уровень \(1\) (можно выбрать подстроку «aa»),
• строки «zzzz» и «zzbzz» имеют уровень \(2\) (можно выбрать две непересекающихся подстроки «zz» в каждой их них),
• строки «abed» и «aca» имеют уровень \(0\) (невозможно выбрать хотя бы одну подстроку длины \(k=2\), которая содержит один различный символ).

Зухаир дал вам целое число \(k\) и строку \(s\) длины \(n\). Вам нужно найти \(x\) — уровень строки \(s\).