UCF

Time limit: 0.2s Memory limit: 2MB Input: ucf.in Output: ucf.out

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 ss format din nn litere mici ale alfabetului. El trebuie să coloreze toate caracterele într-un număr minim de culori diferite. După colorare, el poate schimba oricare 22 caractere vecine din șir care sunt de culori diferite. Această operație poate fi efectuată de oricâte ori (inclusiv 00). 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 nn și ss 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 nn, numărul de caractere.
Pe cea de-a doua linie, se găsește ss, ș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

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

Exemplul 1

ucf.in

9
abacbecfd

ucf.out

2

Explicație

Colorarea din primul exemplu poate fi : 1121212121 1 2 1 2 1 2 1 2.
Aceasta poate fi sortată folosind schimbările: 232-3, 454-5, 676-7, 898-9, 787-8.

Exemplul 2

ucf.in

7
abcdedc

ucf.out

3

Log in or sign up to be able to send submissions!