Az I/S. 70. feladat (2023. március)

I/S. 70. Egy T betűsorozatot palindromnak nevezünk, ha az angol ábécé kisbetűiből áll, és visszafele olvasva megegyezik T-vel. Például az ,,abbfbba'', ,,e'' és ,,tt'' betűsorozatok palindromok, de az ,,ab'', ,,xyz'' és ,,abab'' betűsorozatok nem.

Egy T betűsorozatot szuperpalindromnak nevezünk, ha pontosan egy betűből áll, vagy pedig felírható PxP alakban, ahol P egy szuperpalindrom, x pedig az angol ábécé egy tetszőleges kisbetűje. Például az ,,a'', ,,xyxhxyx'' és ,,aaa'' betűsorok szuperpalindromok, de az ,,aa'', ,,xyxhyxy'' és ,,aabcbaa'' betűsorok nem.

Adott egy $\displaystyle N$ darab betűből álló betűsor. Adjuk meg, hogy minimum hány betűjét kell megváltoztatni ahhoz, hogy egy szuperpalindromot kapjunk.

A bemenet első sorában az $\displaystyle N$ szám található, a betűsor hossza. A második sorban az angol ábécé $\displaystyle N$ darab betűje található, szóköz nélkül.

A kimenet egyetlen sorában egyetlen szám szerepeljen: a minimálisan átírandó betűk száma, hogy szuperpalindromot kapjunk. Ha ez nem lehetséges, írjunk ki $\displaystyle (-1)$-et.

Magyarázat (1. példa): 3 betű megváltoztatásával kaphatjuk például a következő szuperpalindromot: ,,abababa''.

Korlátok: $\displaystyle 1 \le N \le 10^{5}$. Időkorlát: 0,4 mp.

Értékelés: a pontok 50%-a kapható, ha a program helyes kimenetet ad az $\displaystyle N\le 7$ esetekben.

Beküldendő egy is70.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható. A dokumentáció tartalmazza a megoldás elméleti hátterét, az esetleg felhasznált forrásokat. Ne tartalmazzon kódrészleteket, azok magyarázata kódkommentek formájában a forrásprogramban szerepeljen.

(10 pont)

A beküldési határidő 2023. április 17-én LEJÁRT.

Statisztika:

5 dolgozat érkezett.
10 pontot kapott:	Zádor-Nagy Zsombor.
5 pontot kapott:	2 versenyző.
4 pontot kapott:	1 versenyző.
2 pontot kapott:	1 versenyző.

A KöMaL 2023. márciusi informatika feladatai