Pracsiu Dan (dnprx) Se dă un șir de caractere de lungime N format din litere mari ale alfabetului englez și un număr întreg K. Asupra șirului se poate aplica în mod repetat următoarea operație: se alege o subsecvență de lungime cel putin K având toate elementele egale și se elimină din șir. Evident că prima dată operația se aplică asupra șirului inițial și ulterior asupra șirului obținut din aplicarea operației anterioare. Operația se aplică până când șirul devine șirul vid (de lungime 0) sau șirul nu mai conține subsecvențe de lungime cel puțin K cu toate elemente egale.
Cerința
Cunoscând N, K și șirul de caractere, să se determine care este lungimea minimă la care poate fi redus șirul după aplicarea operațiilor într-un mod convenabil.
Date de intrare
Fișierul de intrare zuma.in conține pe prima linie numerele N și K separate prin spațiu și pe a doua linie șirul de caractere format din N litere mari.
Date de ieșire
În fișierul de ieșire zuma.out trebuie să afișați un singur număr natural reprezentând lungimea minimă pe care o poate avea șirul după aplicarea în mod convenabil a operațiilor.
Restricții și precizări
1 ≤ K ≤ N ≤ 500- Pentru teste în valoare de
10puncte25 ≤ K ≤ N ≤ 100 - Pentru alte teste în valoare de
10puncteK = 2 - Pentru alte teste în valoare de
10puncte numărul de caractere distincte din șir este2 - Pentru alte teste în valoare de
15puncte1 ≤ N ≤ 50 - Pentru alte teste în valoare de
35puncte1 ≤ N ≤ 200
Exemplu:
zuma.in
10 3 AAABBBCCCA
zuma.out
0
Explicație
Avem N = 10 și K = 3. Se poate elimina orice subsecvență cu litere identice de lungime cel puțin 3.
Considerând șirul indexat de la 1, la prima operație putem elimina subsecvența [4,6]=BBB pentru că are lungimea 3.
Acum șirul este AAACCCA, deci putem elimina subsecvența [4,6]=CCC, obținând șirul AAAA. Acesta este format din 4 caractere egale, deci îl putem șterge și obținem șirul vid ce are lungimea 0.
Dacă am fi ales la pasul anterior să eliminăm subsecvența [1,3]=AAA și apoi subsecvența CCC, am fi obținut un șir final de lungime 1, format din ultimul A.