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.