Решить задачу Longest Palindromic Substring (LeetCode 5)?

LeetCode 5. Самый длинный палиндромный подстрок. Expand around center — O(n²) время, O(1) память. 2n-1 центров (n одно-символьных + n-1 между символами).

def longestPalindrome(s):
    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return s[l + 1:r]

    best = ''
    for i in range(len(s)):
        odd = expand(i, i)       # нечётная длина
        even = expand(i, i + 1)  # чётная длина
        if len(odd) > len(best):  best = odd
        if len(even) > len(best): best = even
    return best

Альтернативы: DP — dp[i][j] = s[i]==s[j] and (j-i<2 or dp[i+1][j-1]), O(n²) время и память. Manacher's algorithm — O(n), exploiting symmetry (редко нужен на интервью). Связанные: Palindromic Substrings (LeetCode 647) — count вместо longest.