Fișierul intrare/ieșire	litere3.in, litere3.out	Sursă	Runda 1 Infogim 2019 - 7-8
Autor	Vlad Turcuman	Adăugată de	Hai la Olimpiada - Iasi Gimnaziu • ptest
Timp de execuție pe test	0.25 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Litere3

Catalin are un sir de litere A = a1a2a3...an. Lui nu ii plac literele mari, asa ca isi doreste sa gaseasca o subsecventa B din A care sa aiba cat mai multe litere mici distincte, dar sa nu aiba mai mult de K litere mari.

Date de intrare

În fișierul de intrare litere3.in se află pe prima linie numarele N si K iar pe a doua line N litere: a1, a2, ..., aN.

Date de ieșire

Afișați în fișierul litere3.out numarul maxim de litere mici distincte pe care poate sa le aiba B.

Restricții

• 1 ≤ N ≤ 100 000

• 0 ≤ K ≤ N

• Pentru 60% din punctaj: K = 0

Exemplu

Explicație

Exemplul 1 : Subsecventa B cu numar maxim de litere mici distincte e bbaazz (are 0 litere mari, si 3 litere mici distincte).
Exemplul 2 : O subsecventa B cu numar maxim de litere mici distincte e mAbbaazz (1 litera mare, si 4 litere mici distincte). Alte subsecvente posibile sunt: mAbbaazzC si CmAbbaazz