Zadanie

Po tom čo ľudia skolonizovali vesmír, začalo obdobie nudy, ale že brutálnej nudy. Jeden z dôsledkov tejto nudy bol aj nový šport, ale že brutálny šport. Lakťovaná. Pravidlá sú jednoduché (ale že brutálne): je niekoľko tímov s jeden alebo viac hráčmi, hráči sa postavia na rovnú čiaru a ak existuje nejaká dvojica ľudí, ktorí stoja vedľa seba a sú z rôznych tímov, tak sa navzájom ulakťujú (naraz sa ulakťuje stále len jedna dvojica). Toto sa opakuje, až kým sa nemá kto lakťovať. Keďže počet ľudí nie je nekonečný, chceli by sme vás poprosiť, aby ste naprogramovali program, ktorý vypočíta, koľko minimálne ľudí ostane živých, na základe ich počiatočného postavenia.

Úloha

Na prvom riadku vstupu dostanete číslo \(n\), počet hráčov. Na druhom riadku vstupu dostanete reťazec pozostávajúci z malých písmen anglickej abecedy dĺžky \(n\). V každom ťahu môžete eliminovať nejakú dvojicu susedných písmen, ktoré sú rozdielne. Aký najkratší reťazec vie vzniknúť po odstránení takýchto dvojíc ?

Formát vstupu

Na prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 10^6\)) udávajúce počet hráčov Na druhom riadku vstupu je postupnosť malých písmen anglickej abecedy reprezentujúca postavenie daných hráčov.

Máme štyri sady, každá je po 2 body, pre dané sady platia nasledovné obmedzenia:

Sada 1 2 3 4
\(1 \leq n \leq\) \(20\) \(1000\) \(50\,000\) \(10^6\)

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo určujúce minimálny počet ľudí, ktorí po skončení hry prežijú.

Príklady

Input:

3
sss

Output:

3

V prvom príklade sa nemá kto ulakťovať.

Input:

5
aabba

Output:

1

V druhom príklade sa najprv ulakťujú hráči na predposlednej a poslednej pozícii, teda ostane \(aab\). Následne sa ulakťujú hráči na predposlednej a poslednej pozícii a ostane \(a\).

Input:

6
aaazzz

Output:

0

Rozoberme si úlohu po prípadoch, ktoré môžu nastať

  1. Majoritný element: Pretože hľadáme dĺžku najkratšieho stringu, sa v tomto prípade budeme snažiť ulakťovať čo najviac členov majoritného tímu. Teda riešením bude priradiť každého, kto nie je z majoritného tímu k niekomu z majoritného tímu. Teda ak je v nejakom tíme viac hráčov ako všetkých zvyšných hráčov, tak odpoveď je jednoducho \(X - (N - X)\), kde \(X\) je počet hráčov v najpočetnejšom tíme a \(n\) je počet všetkých hráčov. \(N - X\) je počet hráčov všetkých zvyšných tímov, a teda rozdiel počtu hráčov v najpočetnejšom tíme a všetkých zvyšných hráčov je minimálny počet hráčov, ktorým neostane súper, teda prežijú.

  2. Iba jeden tím: Vtedy je odpoveď počet všetkých hráčov, pretože sa nemá kto laktovať.

  3. Ostatné prípady: Všimnime si, že v tomto prípade vieme vytvárať dvojice až kým nám neostane iba jeden alebo nula hráčov. Kedže stále odoberáme po dvoch hráčoch, teda po párnym počte, tak sa nám párita zachová až dokonca. Teda odpoveď je zvyšok po delení dvojkou pôvodného počtu hráčov.

Časová a Pamäťová zložitosť:

Potrebujeme jeden prechod stringom na to, aby sme si zapamätali počty výskytov pre každé písmenko. Písmenká si môžeme pamätať v obyčajnom poli veľkom 26 tak, že a by bolo na indexe 0 a z na indexe 25. Toto vieme v lineárnom čase, teda v O(n).

Ďalej už len nájdeme maximum v poli veľkom 26, čo je O(1), a skontrolujeme pár podmienok, čo je tiež O(1).

Teda celková časová zložitosť je O(n).

Čo sa týka pamäte: Teoreticky si vieme načítavať znaky zo vstupného stringu po jednom a pamätať si len pole veľké 26. Teda pamäťová zložitosť je O(1), samozrejme ale akceptujeme aj keď niekto uviedol O(n).

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.