Условие

Дана строка s; верните самую длинную палиндромную подстроку в s.

Input: s = "babad"

Output: "bab"

Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"

Output: "bb"

#только английские буквы и цифры

Ответ

Расширяйтесь от каждого возможного центра палиндрома: одного символа и промежутка между двумя. Сохраняйте самый длинный найденный интервал; время O(n²), дополнительная память O(1) без учёта результата.

Python:

def longest_palindrome(s: str) -> str:
    start = end = 0
    for center in range(len(s)):
        for left, right in ((center, center), (center, center + 1)):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            if right - left - 1 > end - start:
                start, end = left + 1, right
    return s[start:end]

Для пустой строки возвращается пустая. При равной максимальной длине остаётся первый найденный вариант; для babad это bab, также допустим aba.