Doprogramovanie do: 13. február 2023 23:59
11 dní
Popisy už neodovzdávajte. Ešte stále však môžete odosielať vaše programy, za ktoré dostanete časť bodov.
Počet bodov:
Popis:  12b
Program:  8b

Oslava sa už blížila k jej vyvrcholeniu (teda aspoň pre Miška), a to k slávnostnej večeri. Šéfkuchárka Kika pripravila siahodlhú výzvu pre nejeden žalúdok – večeru pozostávajúcu z postupnosti niekoľkých chodov. Za chod považujeme jeden druh jedla, napríklad polievku alebo dezert. Slávnostná večera môže byť zostavená napríklad takto: polievka, polievka, predjedlo, dezert, polievka – teda päť chodov pozostávajúcich z troch druhov jedál.

Miško, hoci sa večere nevie dočkať, nemôže zabúdať na svoje zdravie. Doktor mu totiž pred touto oslavou dovolil papať iba jeden druh chodu. Ktorý? To už je na Miškovom výbere. Okrem toho mu doktor povedal, že najlepšie bude, keď nebude mať príjem potravy prerušovaný väčšími pauzami. Teda, ak už raz začne papať, bude môcť papať iba pokiaľ sa bude servírovať ten jeho jeden druh chodu. Po zvyšok večere mu potom už ostávajú iba oči pre závisť. Miško ale má jedno eso v rukáve, a to kontakt na šéfkuchárku Kiku. Miško môže Kiku poprosiť, aby niektoré druhy chodu (napríklad polievku a predjedlo) prehlásila za niektorý iný (napr. obe prehlási za dezert). Tým pádom by mohol papať aj všetky polievky, predjedlá a aj všetky dezerty, pričom by sa ale tváril, že to je len jeden druh chodu. Ak Miško poprosí šéfkuchárku Kiku, aby najviac \(k\) druhov chodov prehlásila za iný druh chodu, koľko najviac chodov, bezprostredne po sebe, bude môcť Miško spapať?

Úloha

Dostanete reťazec \(n\) znakov, v ktorom môžete urobiť najviac \(k\) operácií: zmeň všetky znaky X na Y. Vašou úlohou je nájsť dĺžku najdlhšej možnej súvislej podpostupnosti rovnakých znakov, aká sa najviac \(k\) takýmito operáciami dá vytvoriť.

Formát vstupu

V prvom riadku vstupu sú čísla \(n\) (\(1 \leq n \leq 10^6\)), udávajúce počet chodov a \(k\) (\(0 \leq n \leq 100\)), udávajúce počet druhov chodov, ktoré Kika prehlási za iný chod. Nasleduje postupnosť chodov, zložená z malých a veľkých písmen anglickej abecedy a číslic, kde každý znak reprezentuje druh chodu.

Sada 1 2 3 4
\(1 \leq n \leq\) \(100\) \(1\,000\) \(10^4\) \(10^6\)

V prvej sade navyše platí, že reťazec na vstupe je zložený iba z číslic, teda zo znakov 09.

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo, udávajúce najväčšiu dĺžku súvislej podpostupnosti, v ktorej sú všetky chody jedného druhu (po prehlásení najviac \(k\) druhov chodov za iné).

Príklad

Input:

10 2
abbcbadabc

Output:

6

Ak zmeníme b a c na a, dostaneme postupnosť a-čok oddelenú jedným d. Pred d-čkom je táto postupnosť a-čok dlhá 6, čo je ľahko overiteľne najdlhšia podpostupnosť tvorená rovnakým znakom, ktorú z tejto postupnosti vieme vytvoriť.

Input:

20 5
9z2bX3dQquQevLFRmhYH

Output:

7

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.