>ExpInterview_

Longest Palindromic Substring

Medium
StringDynamic Programming

Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Examples

Input: s = "babad"
Output: "bab"
Input: s = "cbbd"
Output: "bb"
Input: s = "a"
Output: "a"

Constraints

  • •1 <= s.length <= 1000
  • •s consists of only digits and English letters.