1-D Dynamic Programming Palindromes
525. Longest Palindromic Substring
You are given a string s. Return its longest substring that is a palindrome.
A substring is a block of letters that sit next to each other in s. A palindrome reads the same
forwards and backwards, such as "level" or "noon". A single letter is a palindrome, so the answer always
has at least one letter.
If several palindromes share the longest length, return the one that starts first, furthest to the left. Answers are shown in double quotes.
Example 1
Input: s = "abaxyzzyxf"
"xyzzyx"Explanation: aba is a palindrome of 3 letters, but xyzzyx has 6. A palindrome can have an even length, with two
equal letters in the middle.
Example 2
Input: s = "abacdc"
"aba"Explanation: aba and cdc both have 3 letters, and no palindrome is longer. aba starts first, so it is the answer.
Example 3
Input: s = "abcd"
"a"Explanation: No two letters are equal, so every palindrome here is a single letter. The first one is a.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ s.length ≤ 3000sholds only lowercase English letters
Clarifying questions
What you would ask an interviewer before writing any code.