Поиск самого длинного подпалиндрома в строке

Java Средний strings

Задача «Поиск самого длинного подпалиндрома в строке»

Дана строка, состоящая из строчных латинских букв. Найдите и выведите самый длинный подпалиндром (подстроку, которая читается одинаково слева направо и справа налево). Если таких подстрок несколько, выведите первую по порядку. Длина строки не превышает 1000 символов.

Формат ввода

На вход подаётся одна строка S (1 ≤ |S| ≤ 1000), состоящая из строчных латинских букв.

Формат вывода

Выведите один искомый подпалиндром.

Примеры

Пример 1

ВВОД

babad

ВЫВОД

bab

Пример 2

ВВОД

racecar

ВЫВОД

racecar

Пример 3

ВВОД

a

ВЫВОД

a

main.java