Problem 2449: UCF

Măricelu tocmai ce a descoperit cum să coloreze și să scrie. Părinții lui îi propun astfel următoarea problemă care să îl ajute să își aprofundeze noile descoperiri:

Ei îi dau un cuvânt reprezentat ca un șir de caractere $s$ format din $n$ litere mici ale alfabetului. El trebuie să coloreze toate caracterele într-un număr minim de culori diferite. După colorare, el poate schimba oricare $2$ caractere vecine din șir care sunt de culori diferite. Această operație poate fi efectuată de oricâte ori (inclusiv $0$ ). Obiectivul este să sorteze șirul de caractere în ordine crescătoare.

Măricelu trebuie să rezolve problema de la părinți cât mai repede!

Cerință

Cunoscând $n$ și $s$ se cere să se găsescă numărul minim de culori ce trebuie folosite pentru colorarea șirului, astfel încât să existe o secvență de operații, oricât de lungă, care îl sortează.

Date de intrare

Pe prima linie a fișierului de intrare ucf.in se găsește $n$ , numărul de caractere.
Pe cea de-a doua linie, se găsește $s$ , șirul de caractere.

Date de ieșire

Pe prima linie a fișierului de ieșire ucf.out se va găsi un singur număr întreg, numărul minim de culori folosite.

Restricții și precizări

$1 \leq n \leq 200 \ 000$ ;
Pentru teste în valoare de $20$ de puncte, $n \leq 5\ 000$ .
Literele identice pot fi colorate cu aceeași culoare sau culori diferite.

Exemplul 1

ucf.in

9
abacbecfd

ucf.out

Explicație

Colorarea din primul exemplu poate fi : $1 1 2 1 2 1 2 1 2$ .
Aceasta poate fi sortată folosind schimbările: $2-3$ , $4-5$ , $6-7$ , $8-9$ , $7-8$ .

Exemplul 2