Танд нэг мөр тэмдэгт мөр (string) өгөгдөнө.

Гэхдээ энэ мөр нь зөвхөн үсэг биш байж болно. Тоо, зай, тусгай тэмдэгтүүд ч орж болно.

Таны даалгавар бол:

1. Тэмдэгт мөрөөс зөвхөн латин үсгүүдийг (a-z, A-Z) авч үлдэнэ.
2. Бүх үсгийг жижиг үсэг (lowercase) болгон хувиргана.
3. Үүссэн шинэ мөр доторх хамгийн урт palindrome substring (дараалсан дэд мөр)-ийг ол.

Хэрэв олон ижил урттай palindrome байвал:

• хамгийн эхэнд байрлах (leftmost)-ийг сонгоно.

Оролт:

Нэг мөрөнд нэг тэмдэгт мөр өгөгдөнө.

Гаралт:

2 мөр хэвлэнэ:

1-р мөр: хамгийн урт palindrome substring-ийн урт
2-р мөр: тухайн palindrome substring

Хязгаарлалтууд:

• 1 ≤ n ≤ 200000
• Мөр нь:
  • латин үсэг (a–z, A–Z)
  • цифр (0–9)
  • зай
  • тусгай тэмдэгтүүд агуулж болно

Дэд бодлого

Жишээ:

Оролт-1

babad

Гаралт-1

3
bab

Тайлбар-1

• Боломжит palindrome-ууд:
  • "bab"
  • "aba"
• Аль аль нь урт 3
• "bab" нь эхэнд байрласан → сонгогдоно

Оролт-2

A man, a plan, a canal: Panama

Гаралт-2

21
amanaplanacanalpanama

Тайлбар-2

• Цэвэрлэсний дараа:

amanaplanacanalpanama

- Бүхэлдээ palindrome → урт нь 21

Оролт-3

abc123cba!!!

Гаралт-3

6
abccba