Longest Palindromic Substring
Longest Palindromic Substring is a medium 1-D Dynamic Programming problem from the Blind 75. The key pattern is expand around centre, and a good solution runs in O(n²) time.
Problem
Return the longest palindromic substring; if tied, return the earliest one.
Examples
Example 1
Input
"forgeeksskeegfor"Output
"geeksskeeg"Example 2
Input
"xabacy"Output
"aba"Example 3
Input
"pqqr"Output
"qq"Approach
Every palindrome has a centre, either a character or the gap between two. Expand outward from all 2n − 1 centres and keep the longest.
| Pattern | Expand around centre |
|---|---|
| Time | O(n²) |
| Space | O(1) |
Watch out for
Remember even-length centres, the gaps between characters.