Q45: Longest Palindromic Substring
Given a string s, return the longest palindromic substring in s using Expand Around Center approach.
Center Expansion Longest Palindrome
function longestPalindrome(s) {
let start = 0;
let maxLength = 0;
function expand(left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
const len = right - left - 1;
if (len > maxLength) {
maxLength = len;
start = left + 1;
}
}
for (let i = 0; i < s.length; i++) {
expand(i, i);
expand(i, i + 1);
}
return s.substring(start, start + maxLength);
}
console.log(longestPalindrome('babad')); // 'bab' or 'aba'💡 Expands outward from odd and even center indices. When expansion breaks, calculates valid length (
right - left - 1) and updates best start index and maxLength.Key Takeaways
- Expands around odd and even centers while keeping track of max substring bounds.
- Runs in $O(n^2)$ time and $O(1)$ auxiliary space.
Knowledge Check
What is the auxiliary space complexity of the Expand Around Center method for Longest Palindromic Substring?