English
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/
Zadanie Słowa (slo)
Words
Memory limit: 32 MB
By a word we mean
a sequence of capital letters of the English alphabet.
The length of a word is the number of letters contained in it.
This way, word 
ABAACBBBA is of length 9.
By a block within a word we understand maximal consistent subsequence of the same letters.
A word is called 
-hard, if it contains 
blocks.
Taking into consideration the word 
, it turns out to be 6-hard, because it consists of
the following blocks: A|B|AA|C|BBB|A.
If two given words are of the same length, it is possible to check how different they are.
Two words of the length 
are 
-different, if for exactly 
positions 
(
), 
'th letter of the first word is different from 
'th letter of the second word.
Checking two words 
and 
AAAABBBBB, it turns out that they are 3-different.
For a given word 
, we want to find not too different word 
, so that it is not too complicated.
Your task is to define, how simple 
can be.
Task
Write a program which:
- reads the numbers
and a word 
of length 
;
- determines the minimal value of
, so that there exists
a 
-hard word 
, which is at most 
-different
from 
(which is, there is no 
, so that 
and 
are 
-different);
- writes the answer to the standard output.
Input
In the first line of the standard input there are two integers 
separated with a single space (
, 
). They represent adequately: the length of the word 
and the
allowed level of difference. In the second line there are exactly
capital letters forming the word 
.
Output
One integer is to be written to the standard output - 
.
Example
For the input data:
9 3 ABAACBBBA
the correct result is:
2
Task author: Tomasz Idziaszek.