Dynamic Programming · LC #5
Longest Palindromic Substring
Find the longest palindromic substring using expand-around-center: for each index try both odd and even expansions, tracking the longest match. O(n²) time, O(1) space.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Return the longest palindromic substring of string `s`.
Sample I/O
Input: s = "babad" Output: "bab" (or "aba") Input: s = "cbbd" Output: "bb"
Intuition
How to Think About It
Intuition
DP (or its space-optimised expand-around-center variant) works because every palindrome has a center, and a palindrome of length k is built by extending a palindrome of length k-2. The key insight is that checking all possible centers in O(n) iterations, each expanding O(n), covers all substrings without redundant work.
Core Concept
For each index i, expand outward for odd-length (center=i) and even-length (center between i and i+1). While s[l]==s[r], extend l--, r++. Track max length and start index. Alternative: 2D DP table dp[i][j]=True if s[i..j] is palindrome.
When to use
Finding longest / counting palindromic substrings; any problem that needs to enumerate all palindromes within a string.
When NOT to use
When you need O(n) - use Manacher's algorithm. When you need all distinct palindromic substrings by value (not position), use suffix arrays or Eertree.
Key Insights
What to Know Cold
- Every palindrome has a unique center; iterating all n centers covers all odd palindromes, n-1 gap centers cover all even ones.
- Expand-around-center achieves O(1) space vs O(n²) for the DP table - prefer it in interviews.
- After expansion stops at (l, r), the palindrome is s[l+1 : r] (exclusive on both ends post-loop).
- Manacher's algorithm solves this in O(n) using previously computed radii - worth knowing for follow-ups.
- The 2D DP formulation: dp[i][j] = (s[i]==s[j]) && (j-i<2 || dp[i+1][j-1]).
1 example
Worked Examples
Find longest palindrome in "raceacar"
s="raceacar"; expected "aceca" or "raceacar".
Expand around each center (odd + even), track max span.
Output: "raceacar" → "raceacar" (full string is palindrome)
Template for all palindrome-center problems; Palindromic Substrings (LC 647) is a trivial counter variant of this exact pattern.