Longest Palindromic Substring: Expand around center Pattern

Learning Outcome

After this lesson, you should be able to use the symmetry of palindromes and expand from centers instead of generating every substring.

Problem Statement

Given a string s, return the longest palindromic substring in s. The substring must be contiguous.

Brute Force Approach

Generate every substring and check whether it is a palindrome. Keep the longest valid one.

This is very direct, but checking many substrings and validating each one can reach O(n^3).

Optimized Approach

Every palindrome has a center. For each index, expand once for odd-length palindromes and once for even-length palindromes. Track the best range found.

Exact Pseudocode

bestStart = 0
bestLength = 1
expand(left, right):
  while left >= 0 and right < length(s) and s[left] == s[right]:
    update best range if right - left + 1 is larger
    left = left - 1
    right = right + 1
for center from 0 to length(s) - 1:
  expand(center, center)
  expand(center, center + 1)
return substring(bestStart, bestLength)
  

Reference Code

class Solution:
    def longestPalindrome(self, s):
        if not s:
            return ""

        best_start = 0
        best_len = 1

        def expand(left, right):
            nonlocal best_start, best_len
            while left >= 0 and right < len(s) and s[left] == s[right]:
                length = right - left + 1
                if length > best_len:
                    best_start = left
                    best_len = length
                left -= 1
                right += 1

        for center in range(len(s)):
            expand(center, center)
            expand(center, center + 1)

        return s[best_start:best_start + best_len]
  

Sample Dry Run

Complexity

Edge Cases

• Empty string if platform allows it.
• Single-character string.
• Even-length palindrome such as "bb".

Interview Checklist

• Handle both odd and even centers.
• Track indices, not only the substring.
• Return any valid longest palindrome if multiple exist.

FAQs