Longest palindromic substring

Problem

Find the longest part of a word that reads the same in both directions. If several parts have the same length, print the one that starts first.

Example 1

Input

babad

Output

bab

bab and aba both have length 3; bab starts first.

Example 2

Input

cbbd

Output

bb

bb.

Try the problem first. Open one hint at a time.

Hint 1

Every palindrome grows outward from a centre that is a letter or a gap between two letters.

Hint 2

Expand from each centre while both ends match, and keep the longest result.

Write your Python code, run it on the examples and submit it to hidden tests.