Longest Palindromic Substring
Medium · dynamic programming
Given a string s, find the longest substring that reads the same forwards and backwards (a palindrome), and return that substring. A substring is a run of neighbouring characters, so "bcd" is a substring of "abcde" but "ace" is not.
Several palindromes can share the longest length. In that case return the one that starts earliest in s.
A single character is a palindrome, and s is never empty, so there is always an answer.
Examples
Example 1
Input: s = "babad"
Output: "bab"
Both "bab" and "aba" have length 3. "bab" starts earlier, so it is the answer.
Example 2
Input: s = "cbbd"
Output: "bb"
The only palindrome longer than one character is "bb".
Example 3
Input: s = "abcd"
Output: "a"
No two neighbouring characters match, so every palindrome has length 1 and the first one wins.
Constraints
- 1 <= len(s) <= 1000
- s consists of lowercase letters and digits