Bizga s string berilgan. Undan eng uzun palindrom substringni topish kerak. s string uzunligi 1 va 1000 belgi orasida bo’ladi.
Misol:
Input: s = "babad" Output: "bab" Tushuntirish: "aba" ham to'g'ri javob.
Palindrom deb, o’ng va chap qismi bir-biriga simmetrik bo’lgan so’zlarga aytiladi. Ya’ni so’zni ohiridan boshiga o’qiganda ham bir xil so’z chiqadi. Masalan:
aziza, amma, kiyik, kallak, tabobat, …
Ba’zi so’zlarning qismida esa palindrom mavjud: ananas, baobab, …
Ishlash tartibi
Masalani ishlashning turlicha – bruteforce, dynamic programming, expand around center usullari mavjud. Biz qisqaroq bo’lgani uchun expand around center algoritmini ko’rib o’tamiz.
Har bir palindrom aslida markazida bitta yoki ikkita harf joylashgan oynali so’z. Masalan «anana» so’zida o’rtadagi a harfi – markaz, abba so’zida esa markaz – bb. Bu faktni hisobga olgan holda, markazdan boshlab tekshirib chiquvchi funksiya yozish mumkin.
Dastlab, sikl ichida so’zning har bir harfini markazligiga tekshiramiz.
- banana. b – markaz, uning chap tarafida harf yo’q, demak maksimum palindrom «b»ga teng.
- banana. a – markaz, uning chap tarafida b, o’ng tarafida n mavjud, demak ban palindrom emas, a ning o’zi palindrom. Bizda eng uzun palindrom b bo’lib turgani uchun, uning o’zini qoldiramiz.
- banana. n – markaz, uning chap va o’ng tarafida bir xil – a harfi bor. Hozircha bizda ana palindromi hosil bo’ldi. Tekshirishni chap va o’ng tarafga davom ettiramiz. Bu safar banan – palindrom emas. Demak hozir bizda banana so’zida ana palindromi topildi.
- banana. a – markaz. uning chap va o’ng tarafida bir xil – n harfi bor. Hozircha bizda nan palindromi hosil bo’ldi. Tekshirishni chap va o’ng tarafga davom ettiramiz va anana palindromini topamiz. Chap va o’ngga yana kengaytira olmaymiz, sababi chapda b harfi bo’lsa, o’ng tarafi bo’sh qoldi. Demak hozir bizda banana so’zida anana palindromi topildi. anana palindromi ana palindromidan uzunroq bo’lgani uchun bizda maksimum palindrom hozircha anana.
- banana. n – markaz. Chap va o’ng tarafida bir xil – a harfi bor. Hozircha bizda ana palindromi hosil bo’ldi. Tekshirishni chap va o’ng tarafga davom ettira olmaymiz, chunki ana ning o’ng tarafida harf yo’q. ana palindromi anana dan kalta bo’lgani uchun anana palindromi eng uzunligicha qoladi.
- banana. a – markaz. O’ng tarafida harf yo’q. Palindrom a ga teng. U anana palindromidan kalta, shu sababli eng uzun palindrom – anana ligicha qoladi.
Yuqoridagi kodning muammosi shundaki, u markazi ikki harfli palindromlarni topmaydi. Masalan sabbad so’zida palindrom abba bo’lsa ham, kod s ni palindrom sifatida qaytaradi.
Kodni optimizatsiya qilib quyidagicha ko’rinishga olib kelamiz: