Explain how to find the longest palindromic substring.

Difficulty: 6/10

center expansion, Manacher's algorithm, dynamic programming

Longest Palindromic Substring

A palindrome reads the same from left to right and right to left. A practical approach for the longest palindromic substring is expand-around-center: every palindrome has a center, which can be a character for odd-length palindromes or a gap between characters for even-length palindromes.

javascript

1
Expand-around-center takes O(n²) time in the worst case.
2
Auxiliary space is O(1), excluding the returned substring.
3
Dynamic programming can also solve the problem in O(n²) time and O(n²) space.
4
Manacher's Algorithm solves the problem in O(n) time but is more complex.
5
For production code, I would choose the approach based on input size and maintainability requirements.

Scenario Questions

0-2 years experience

1We have a function that receives a short user‑entered string (max 100 chars) and we need to return its longest palindromic substring. How would you implement it quickly?
2If you wrote a simple expand‑around‑center solution and it fails on the input 'abacdfgdcaba', what bug might be causing the wrong result?
3What edge cases would you test for after implementing your solution?

Follow-up Questions

What would happen if the input string is extremely long, say 10⁶ characters?
How would you modify your solution to also return the start index of the palindrome?
Can you discuss the memory trade‑offs between the DP and Manacher approaches?