Longest Palindromic Substring
Return the longest substring of s that is a palindrome.
A way to picture it
Drop a pebble in a pond and ripples spread out evenly in both directions. Every palindrome is a ripple around a center. Drop a pebble at every letter and every gap between letters, and watch how far each ripple spreads before the edges stop matching.
How to approach it
Try all 2n − 1 centers (letters and gaps). Expand outward while both ends match, and keep the longest.
Example
Input: {"s":"babad"}. Output: "bab".
Complexity: O(n²) time and O(1) space. 2n − 1 centers, each expanding up to n/2 steps.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.