Longest Palindromic Substring
MediumDynamic Programming
You are given a string s. Return the longest contiguous substring of s that is a palindrome, meaning it reads the same forwards and backwards.
If several palindromic substrings share the maximum length, return the one that starts earliest in s.
Example 1
- Input:
- s = "abcbaxyx"
- Output:
- "abcba"
- Explanation
abcba(length 5) andxyx(length 3) are palindromes; the longer one wins.
Example 2
- Input:
- s = "abab"
- Output:
- "aba"
- Explanation
- Both
aba(starting at index 0) andbab(starting at index 1) have length 3, so return the earlier one.
Example 3
- Input:
- s = "forgeeksskeegfor"
- Output:
- "geeksskeeg"
- Explanation
- This palindrome has even length 10, centred between the two
scharacters, so the search must try centres between characters as well as on them.
Constraints
- 1 ≤
s.length≤ 1000 sconsists of English letters and digits