Longest Palindromic Substring

Problem

Given a string s, return the longest contiguous substring of s that reads the same forwards and backwards. If several substrings tie for longest, any one of them is acceptable.

• The string is up to 1,200 characters.
• s consists of digits and English letters.

Examples

• s = "xyzabaqr" → "aba". An odd-length palindrome centred on the middle b.
• s = "xyabbaq" → "abba". An even-length palindrome; its centre sits between the two b's.
• s = "q" → "q". A single character is trivially a palindrome.

Hints

1. Every palindrome has a centre. How many possible centres does a string of length n have, counting the gaps between characters?
2. From a given centre, how far can you grow outward while the ends still match? Does growing ever undo a smaller palindrome?
3. Expand around each of the 2n-1 centres; keep the widest. Alternatively, dp[i][j] = s[i]==s[j] and dp[i+1][j-1].