How do you find the longest palindromic substring in a string?
Every palindrome has a centre. Try each index as an odd-length centre and each gap between letters as an even-length centre, expand outward while the ends match, and keep the longest.
Explain it simply
A palindrome is like a mirror with a middle point. In "racecar" the middle is the letter "e"; in "abba" the middle is the gap between the two b letters.
So there are only about 2n possible centres. For each one, put two fingers on the middle and push them apart as long as the letters on both sides are equal. Remember the longest stretch you find.
Example
function longestPalindrome(s) {
let start = 0;
let maxLen = 0;
function expand(l, r) {
while (l >= 0 && r < s.length && s[l] === s[r]) {
l--;
r++;
}
const len = r - l - 1;
if (len > maxLen) {
maxLen = len;
start = l + 1;
}
}
for (let i = 0; i < s.length; i++) {
expand(i, i); // odd length
expand(i, i + 1); // even length
}
return s.slice(start, start + maxLen);
}
console.log(longestPalindrome("babad")); // Output: bab
console.log(longestPalindrome("cbbd")); // Output: bbComplexity
Time O(n squared), space O(1).
What to say in the interview
"I expand around every centre, both odd and even, and track the longest palindrome. That is O(n squared) time and O(1) space, and it is much simpler than the dynamic programming table, which is also O(n squared) but needs O(n squared) space. Manacher's algorithm gets O(n) but is rarely expected."
Common mistakes
- Handling only odd-length palindromes and missing cases like "abba".
- Wrong substring bounds after expanding: the palindrome starts at l + 1, not l.