Longest Palindromic Substring medium
Description
Given a string s, return the longest palindromic substring in s.
Examples
> Case 1:
s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
> Case 2:
s = "cbbd"
Output: "bb"Constraints
1 <= s.length <= 1000sconsists of only digits and English letters.
State design / Intuition
Approach 1: Expand around center — O(n²) time, O(1) space
Every palindrome has a center. For odd-length palindromes the center is a single character; for even-length it’s the gap between two characters. There are 2n - 1 centers to try. For each center, expand outward while characters match.
This is the cleanest approach for interviews. Simple, correct, and clearly O(n²).
Approach 2: Manacher’s algorithm — O(n) time
Augment s with # separators (so all palindromes become odd-length), then use the mirror trick to extend the palindrome radius array p in amortized O(1) per center. Details on the Advanced Patterns page.
For s.length <= 1000 (the constraint here), the O(n²) approach is perfectly fine. Present both in the interview; implement Manacher’s if asked for the optimal.
Code — Expand around center (O(n²))
Code — Manacher’s O(n)
For the interview, lead with expand-around-center. It’s short, obviously correct, and handles all cases without special-casing. Only pivot to Manacher’s if the interviewer asks for O(n). Manacher’s has more moving parts and is harder to debug under pressure.
Analysis
| Approach | Time | Space |
|---|---|---|
| Expand around center | O(n²) | O(1) |
| Manacher’s | O(n) | O(n) |
| DP (2D table) | O(n²) | O(n²) |
Same skin
- Count Palindromic Substrings — same expand-around-center, count instead of track maximum.
- Palindromic Substrings (LC 647) — direct application of Manacher’s
parray. - Shortest Palindrome — find the longest palindrome prefix, then prepend the reverse of the suffix.
- Palindrome Pairs — combine with a trie; different technique but palindrome structure matters.