38. Longest Palindromic Substring

Difficulty: medium · String, Dynamic Programming

Problem

Given a string `s`, print its longest substring that reads the same forwards and backwards. If several palindromic substrings share the maximum length, print the one that starts earliest.

Input

A single line containing the string `s`.

Output

Print the longest palindromic substring.

Example 1

Input:
babad
Output:
bab

Explanation: 'bab' and 'aba' both have length 3; 'bab' starts first.

Example 2

Input:
cbbd
Output:
bb

Explanation: The longest palindrome is 'bb'.

Constraints

- 1 <= |s| <= 1000 - `s` contains only lowercase English letters

Solutions are judged against 2 sample and 10 hidden tests. Sign in to solve it · All problems