💬 Discord
Sign In
NeetCode #666LC-5Medium1-D Dynamic ProgrammingBlind 75NC 150NC 250
← Back to All Problems

#666 · #5 · Longest Palindromic Substring(最长回文子串)

📌 Problem Statement & Constraints

Given a string s, return the longest palindromic substring in s. A palindrome reads the same forwards and backwards. Constraints: 1 <= s.length <= 1000, and s consists of digits and English letters.

💡 Core Algorithmic Approaches

  1. A palindrome expands symmetrically around a center, and there are 2n - 1 centers: n single-character (odd) and n - 1 between-character (even) centers.
  2. For each center, expand outward while the two characters match, tracking the longest span found.
  3. This is O(n^2) time and O(1) extra space, comfortably within the n <= 1000 bound.
  4. Manacher's algorithm achieves O(n), but expand-around-center is simpler and is the standard interview answer.

💻 Benchmark Python3 Implementation

class Solution:
    def longestPalindrome(self, s: str) -> str:
        start, max_len = 0, 1

        def expand(l: int, r: int) -> int:
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            return r - l - 1            # length of the palindrome around this center

        for i in range(len(s)):
            odd = expand(i, i)          # odd-length centers
            even = expand(i, i + 1)     # even-length centers
            cur = max(odd, even)
            if cur > max_len:
                max_len = cur
                start = i - (cur - 1) // 2
        return s[start:start + max_len]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2): each of the 2n - 1 centers expands at most n steps.
💾 Space Complexity
O(1): only indices plus the returned substring.

⚠️ Interview Pitfalls & Follow-ups

  • Checking only odd-length centers: even-length palindromes such as abba require the between-character centers.
  • Recomputing the left end incorrectly: for a center at i and length L, the left end is i - (L - 1) // 2.
  • Using a 2-D DP table: it is correct but costs O(n^2) space for no benefit at this input size.
  • Assuming a single character is not a palindrome: any length-1 substring is one, so initialise max_len to 1.