Longest Palindromic Substring medium
Description
Given a string s, return the longest palindromic substring in s.
Examples
> Case 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
> Case 2:
Input: s = "cbbd"
Output: "bb"Constraints
1 <= s.length <= 1000sconsists of only digits and English letters
Approach 1: Brute Force
Check every possible substring and verify if it is a palindrome.
Approach 2: Expand Around Center (Optimal)
For each position in the string, try to expand a palindrome outward. There are 2n - 1 possible centers (each character + each gap between characters).
Expanding around centers in "babad"
Step 1 of 7
b
[0]a
[1]b
[2]a
[3]d
[4]Center at index 0: expand 'b'. Can't expand further. Length = 1.
Explanation
- A palindrome mirrors around its center
- For odd-length palindromes (like “aba”), the center is a single character
- For even-length palindromes (like “abba”), the center is between two characters
- For each of the 2n - 1 centers, expand outward while characters match
- Track the longest palindrome found during expansion
Why “Expand Around Center” and not DP? Both are O(n^2), but expand-around-center uses O(1) space while the DP table uses O(n^2) space. In interviews, interviewers appreciate the cleaner approach. There is also Manacher’s algorithm which achieves O(n) but is rarely expected in interviews.
Analysis
- Time Complexity:
O(n^2)— n centers, each expansion is up to O(n) - Space Complexity:
O(1)— only uses a few variables