Find the longest palindromic substring by expanding around centers.
Problem Statement
Given a string `s`, return the longest palindromic substring in `s`.
Examples
Input: s = "babad"
Output: "bab"
Explanation: Combining the input according to Longest Palindromic Substring logic yields "bab".
Input: s = "cbbd"
Output: "bb"
Explanation: Combining the input according to Longest Palindromic Substring logic yields "bb".
Complexity
Time Complexity: O(N²)
Space Complexity: O(1)
Hints
💡 Hint 1:
A palindrome mirrors around its center.
💡 Hint 2:
There are 2N - 1 possible centers: N single-character centers (odd length) and N - 1 two-character centers (even length).
💡 Hint 3:
For each center, expand outward while characters match and record the maximum length found.
Editorial & Approach
Problem Overview & Intuition
Every palindrome expands outward symmetrically from a center. A string has N single-character centers (for odd palindromes) and N - 1 between-character centers (for even palindromes). Expanding from all 2N - 1 centers runs in O(N²) time and O(1) space.
Step-by-Step Approach
- If
s.length <= 1, returns. - Initialize
start = 0, maxLen = 1. - Iterate
ifrom0tos.length - 1: - Expand around
(i, i)for odd-length palindromes. - Expand around
(i, i + 1)for even-length palindromes. - Return
s.substring(start, start + maxLen).
Optimal Implementation (JavaScript)
function longestPalindrome(s) {
if (!s || s.length < 2) return s;
let start = 0, maxLen = 1;
function expand(l, r) {
while (l >= 0 && r < s.length && s[l] === s[r]) {
if (r - l + 1 > maxLen) { start = l; maxLen = r - l + 1; }
l--; r++;
}
}
for (let i = 0; i < s.length; i++) {
expand(i, i);
expand(i, i + 1);
}
return s.substring(start, start + maxLen);
}Complexity Analysis
Time Complexity
O(N²) — expanding around 2N - 1 centers.
Space Complexity
O(1) auxiliary space.
Edge Cases & Corner Traps Handled
- Single character string: returns that character.
- Entire string is palindrome: returns entire string.
- All distinct characters: returns any single character (length 1).