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.