Primetimo da ćemo u jednom potezu pretvoriti najmanje 3, a najviše 5 karaktera u $*$. Rešićemo ovaj problem primenom dinamičkog programiranja. Označimo $dp[i][k][m]$ kao najveći broj karaktera koje možemo da pretvorimo u $*$ ako gledamo samo sufiks od indeksa $i$ nadalje, možemo da pretvorimo najviše $k$ karaktera, a $m$ nam govori da li smo prethodni karakter pretvorili u $*$ ili ne. Za slučaj kada je $i>n$ ($n$ je dužina stringa), rešenje je 0. Ako znamo da smo poslednji karakter transformisali u $*$, možemo da zaključimo koji karakter smo transformisali neki od prethodnih elemenata da bi ih transformisali u $*$. Tacnije za prethodni karakter (na poziciji $i-1$), možemo da zaključimo šta je on bio na početku (pre svih transformacija) i u trenutku pre nego što je postao $*$ (karakter koji se pojavljuje najviše puta na pozicijama $i-1,i-2,i-3$ je jedini kandidat), nazovimo ova dva karaktera $prethodniPre$ i $prethodniPosle$.

Jedan od mogućih prelaza je da trenutni karakter ne pretvorimo u $*$. Ovo možemo da uradimo ako prethodni karakter takođe nismo transformisali ($k=0$) ili prethodni karakter nije bio isti kao trenutni u trenutku transformacije ($prethodniPosle \neq s[i]$, gde je $s$ dati string). Formula za ovaj prelaz: $dp[i][k][m]=dp[i+1][k][1]$.

Svi ostali prelazi uzimaju da trenutni karakter i određen broj karaktera posle njega transformišemo u $*$. Isto kao što smo mogli da zaključimo karakter u koji smo promenili prethodni karakter pre nego što je postao $*$, možemo da zaključimo i u koji karakter treba da promenimo trenutni karakter ( ili neki karakter posle njega) kako bi ga transformisali u $*$ (karakter koji se pojavljuje najviše puta na pozicijama $i,i+1,i+2$ je jedini kandidat). Kao i za prethodni karakter definisaćemo 2 karaktera $trenutniPre$ i $trenutniPosle$ po istim pravilima samo za trenutni karakter (karakter na poziciji $i$ umesto $i-1$). Možemo da vidimo da je transformaciju trenutnog karaktera nemoguće izvršiti ako je $prethodniPosle = trenutniPre$ i $prethodniPre = trenutniPosle$. Ovo je bitno proveriti zbog slučajeva poput aababb, gde je rešenje $4$ a ne $6$.

Posmatrajmo slučaj kada hoćemo da tranformišemo trenutni i sledeća 2 karaktera u $*$ (slučajevi za 4 i 5 karaktera se rade na isti način). Transformiasnje trenutnog i sledeća 2 karaktera je moguće uraditi samo kada se tačno jedan od njih razlikuje od $trenutniPosle$. Formula za ovaj prelaz: $dp[i][k][m]=dp[i+3][k-1][0]$

Rešenje za stanje je maksimum od svih mogućih prelaza (ili minus beskonačno ako nijedan nije moguć). Konačno rešenje problema se nalazi u stanju $dp[0][k][1]$.

Zadatak je preuzet sa $\texttt{Moscow}$ $\texttt{Autumn}$ $\texttt{Workshop}$ $\texttt{2019}$ $\texttt{Day}$ $\texttt{1}$, takmičenje $\texttt{Welcome}$ $\texttt{Contest}$ $\texttt{from}$ $\texttt{Asia}$.

Hvala Nikoli Pešiću za pomoć i pisanje editoriala za zadatak.