Longest Palindromic Substring
The problem
Return a longest contiguous substring that reads the same forward and backward. If several have the same maximum length, any is acceptable.
Example
"cabbad" → "abba"
Need a hint?
A palindrome grows symmetrically around a character or a gap.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
For each index, expand around both an odd-length center (i, i) and an even-length center (i, i+1). Stop at a mismatch or boundary. Record only the best start and length while searching, then slice once at the end. Empty input returns an empty string.
Complexity
O(n²) time and O(1) auxiliary space excluding the returned substring.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.