Problem description

Back
Show PDF
Kolorowanie Alfabetu
(D)
Limit pamięci: 256 MB
Limit czasu: 1.00 s

Jaś niedawno zaczął chodzić do szkoły. Jego ulubionymi zajęciami są kolorowanie oraz uczenie się alfabetu. Jaś uznał, że fantastycznym pomysłem byłoby połączenie tych dwóch pasji i pokolorowanie alfabetu.

Jaś napisał sobie pewne słowo (bardzo długie i niekoniecznie będące prawdziwym słowem). Postanowił, że dla każdej litery alfabetu pokoloruje wszystkie wystąpienia tej litery w swoim słowie na ten sam kolor. Jaś zastanawia się, jak bardzo kolorowe może być słowo po pokolorowaniu. Kolorowość słowa rozumie jako liczbę jednokolorowych bloków danego pokolorowanego słowa, gdzie blok to maksymalny przedział liter o tym samym kolorze. Pomóż mu – podaj maksymalną osiągalną kolorowość słowa Jasia.

Wejście

W pierwszym wierszu wejścia znajduje się liczba naturalna N. W drugim i ostatnim wierszu wejścia znajduje się słowo składające się z N znaków – słowo Jasia. W słowie tym występuje tylko 12 pierwszych liter alfabetu: A, B, C, D, E, F, G, H, I, J, K, L (Jaś jeszcze nie nauczył się innych). Wszystkie litery na wejściu są wielkie (Jaś jeszcze nie nauczył się pisowni małych).

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna się znaleźć pojedyncza liczba naturalna – maksymalna możliwa kolorowość słowa Jasia po kolorowaniu. Jaś ma przy sobie tylko 3 kredki: czerwoną, zieloną i niebieską, więc rozważamy jedynie kolorowania korzystające z maksymalnie 3 kolorów.

Ograniczenia

1 ≤ N ≤ 106.

Przykłady

Wejście Wyjście Wyjaśnienie 
10
AAAAAAAAAA
 
1

Dowolne kolorowanie alfabetu skutkuje pokolorowaniem całego słowa na jeden kolor, więc maksymalna kolorowość wynosi 1.
Wejście Wyjście Wyjaśnienie 
12
AAAABBBCCCCC

3

Maksymalna kolorowość wynosi 3. Realizuje ją np. kolorowanie A na czerwono, B na zielono i C na niebiesko. Kolor pozostałych liter nie ma znaczenia.
Wejście Wyjście Wyjaśnienie 
12
ABCDEFABCDEF
 
12

Możemy pokolorować alfabet następująco: litery A i D na czerwono, B i E na zielono, C i F na niebiesko, a pozostałe litery dowolnie, otrzymując maksymalną możliwą kolorowość, czyli 12.
Wejście Wyjście Wyjaśnienie 
12
ABCDBCADCADB
 
11

Maksymalna kolorowość wynosi 11.

Ocenianie

Podzadanie Dodatkowe warunki Punkty
1 N ≤ 100 50
2 Brak dodatkowych ograniczeń 50