DRŽAVNO NATJECANJE 2015. – Prvi dan natjecanja / Srednja škola, II. podskupina (3. i 4. razred) - 2. zadatak

Mirko se sakrio od orkanskog vjetra te se doma igra s nizom znakova upisanim u datoteku na njegovom računalu.

Na početku igre, niz se sastoji od N velikih slova engleske abecede. U svakom koraku Mirko:

1. Odabere dva jednaka slova u nizu.
2. Uveća broj bodova za broj znakova između dva odabrana slova (uključujući i ta dva slova).
3. Izbriše oba odabrana slova.

Igra završava kada Mirko ne može više napraviti niti jedan potez.

Napišite program koji će za zadani niz odrediti najveći mogući ukupni broj bodova koji Mirko može dobiti.

Ulazni​ podaci

U prvom redu nalazi se prirodni broj N (N ≤ 200000) koji označava broj znakova.

U drugom redu nalazi se niz od N velikih slova engleske abecede.

Izlazni podaci

U prvi i jedini red ispišite traženi najveći mogući ukupni broj bodova.

Napomena: Preporučamo da za računanje i ispis rezultata koristite 64-bitni cjelobrojni tip podataka (int64 u Pascalu, long long u C/C++).

Primjeri test​ podataka

Ulaz

5
ABBBA

Izlaz

8

Objašnjenje

Pojašnjenje prvog primjera: Najveći broj bodova možemo dobiti najprije birajući slova A za 5 bodova te zatim dva vanjska slova B za 3 boda.

Kada bismo to učinili obrnutim redoslijedom ukupan broj bodova bi bilo 3 + 3 = 6.

Ulaz

7
ACBABAC

Izlaz

14