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.
Write a program which:
and a word
of length
;
, so that there exists
a
-hard word
, which is at most
-different
from
(which is, there is no
, so that
and
are
-different);
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
.
One integer is to be written to the standard output -
.
For the input data:
9 3 ABAACBBBA
the correct result is:
2
Task author: Tomasz Idziaszek.
W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem szkopul@fri.edu.pl.
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, odwiedź nasze serwery na Discordzie. Są one moderowane przez społeczność, ale członkowie zespołu wsparcia również aktywnie się tam udzielają.