Môžeme sa zamyslieť: Vie nastať situácia, kedy sú v rade aj ľudia, aj psy, ale nikde človek nesusedí so psom? Evidentne nie. Prečo? Lebo každý súvislý úsek ľudí je na krajoch zakončovaný koncom rady alebo psom. Rovnako to funguje aj keď psov a ľudí vymeníme. A keďže máme aspoň dva súvislé úseky (aspoň jeden úsek ľudí a aspoň jeden úsek psov) a iba dva konce radov, tak niekde musí susediť človek so psom.

Čiže pokiaľ existuje v rade aspoň jeden človek a aspoň jeden pes, tak existuje dvojica, ktorú môžeme vymazať. Toto opakujeme, pokiaľ sú v rade aj psy aj ľudia. Každá adopcia zmenší počet ľudí aj psov o 1, čiže na konci dňa ostanú buď iba ľudia alebo iba psy. Takže minimálny počet znakov, ktoré ostanú na konci je $|\text{počet psov} -\text{počet ľudí}|$.

Záleží na poradí ľudí a

psov v rade?

Nie, lebo v našich úvahách vyššie sme nikdy nepredpokladali, že ľudia a psy sú zoradené nejako špeciálne. Vždy sme len hovorili, že ak sú v rade aspoň jeden človek a aspoň jeden pes, tak existuje dvojica susediacich ľudí a psov, ktorých môžeme vymazať. Čiže ak by sme zmenili poradie ľudí a psov, tak by sa nič nezmenilo.

Časová zložitosť

Časová zložitosť je $O(n)$, keďže potrebujeme prejsť celý rad a spočítať počet ľudí a psov.

Pamäťová zložitosť

Záleží, či načítavame celý rad do pamäte, a potom ho spracovávame, alebo či načítame iba jeden znak, spracujeme ho a potom načítame ďalší znak. V prvom prípade je pamäťová zložitosť $O(n)$, v druhom prípade je pamäťová zložitosť $O(1)$. Na plný počet bodov stačila implementácia s pamäťovou zložitosťou $O(n)$.

Vzorový python kód má pamäťovú zložitosť $O(n)$, pretože načítava celý rad do pamäte. Vzorový C++ kód má pamäťovú zložitosť $O(1)$, pretože načítava iba jeden znak naraz.

N = int(input())
s = input()

psi = 0
ludia = 0
for ch in s:
    if ch == 'P':
        psi += 1
    else:
        ludia += 1

print(abs(psi - ludia))

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N;
    cin >> N;

    int psi = 0;
    int ludia = 0;
    for (int i = 0; i < N; i++)
    {
        char x;
        cin >> x;
        if (x == 'P')
            psi++;
        else
            ludia++;
    }

    cout << abs(psi - ludia) << "\n";
}