Given a string s, return its longest substring that reads the same forwards and backwards. When several palindromic substrings tie for longest, return the one that starts earliest in s — "babad" holds both "bab" and "aba", and the answer here is "bab".
Examples
Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is just as long but starts later.
Example 2:
Input: s = "cbbd"
Output: "bb"
Example 3:
Input: s = "a"
Output: "a"
Example 4:
Input: s = "andstopsspotsand"
Output: "stopsspots"
Constraints
1 <= s.length <= 1000
s consists of lowercase English letters and digits.
Prerequisites
Dynamic programming — being able to say, in one sentence, what a single cell of your table MEANS. Everything else follows from that sentence. Rolling variables: when a state only looks back one or two steps, the table collapses to a couple of numbers.
How to think about it
1. Expand Around Every Center Optimal
Intuition
Every palindrome has a centre — a character for odd lengths, the gap between two for even — and there are only 2n-1 of them. Grow outward from each while the ends match, and the longest span wins. Comparing with STRICTLY greater keeps the earliest of equal-length winners, which is the tie-break this problem pins.
Algorithm
1. For each index, treat it as an odd centre and as the left of an even centre. 2. Expand while both ends are in range and equal. 3. Record the span when it beats the best strictly.
Time & Space
Time O(n^2). Space O(1). Manacher's algorithm reaches O(n) and is worth naming, not writing.