Решение задачи LeetCode №5: Longest Palindromic Substring

Рисунок: LeetCode №5: Longest Palindromic Substring

Условие задачи

Дана строка s. Нужно найти самую длинную подстроку, которая является палиндромом.

Палиндром — это слово, которое читается одинаково слева направо и справа налево.

Примеры:

Ввод: s = "babad"

Вывод: "bab" или "aba" (оба — палиндромы)

Ввод: s = "cbbd"

Вывод: "bb"

Подход: Расширение от центра (Expand Around Centers)

Каждый палиндром имеет центр.
Мы можем:

1. Перебрать все возможные центры
2. От каждого центра расширяться влево и вправо, пока символы совпадают
3. Запоминать самый длинный палиндром

Центр может быть:

• Один символ → нечётная длина: "aba"
• Между двумя символами → чётная длина: "abba"

Рисунок: первая часть листинга метода longestPalindrome

Рисунок: вторая часть листинга метода longestPalindrome

Рисунок: листинг метода expandFromCenter

Объяснение словами 5-летнего ребёнка

Представь, что у тебя есть лента с буквами:
b a b a d

Ты хочешь найти самый длинный кусочек, который читается одинаково в обе стороны, как "мам", "поп", "казак".

Ты берёшь одну букву и смотришь:

• "b" — это палиндром (одна буква)
• А теперь смотришь влево и вправо: b a b → b слева и b справа — одинаковые! → "bab" — палиндром!

Потом берёшь две буквы:

• "ba" — разные → не палиндром
• "ab" — разные → не палиндром
• "ba" — снова нет

Потом смотришь на "a" посередине:

• a → b a b → a b a → опять "aba" — палиндром!

Ты находишь два кусочка: "bab" и "aba" — оба длиной 3.

Ты говоришь: "Самый длинный палиндром — 3 буквы!"
И возвращаешь один из них.

Заключение

Примера кода, рассмотренного в статье можно найти по адресу:

https://github.com/ShkrylAndrei/leetcode/blob/main/src/main/java/info/shkryl/task5_longestPalindromicSubstring/Solution.java