Longest Palindromic Substring

Find the longest substring (contiguous) that reads the same forwards and backwards. If several have the maximum length, print the one that starts leftmost.

Input: one line s (lowercase letters and digits).

Output: the longest palindromic substring.

Constraints: 1 ≤ length of s ≤ 2000.

Think about it: every palindrome has a centre — a character (odd length) or a gap between two characters (even length). Expand around each of the 2n − 1 centres: O(n²) time, O(1) memory. (Manacher's algorithm does it in O(n), if you are curious.)