最長回文子字串

題目敘述

小宇在整理一排字母貼紙，想找出貼紙上最長的一段「正著讀、倒著讀都一樣」的連續字母。

給定一個字串 s，請輸出 s 中最長的回文連續子字串。若有多個長度相同的答案，輸出起點最靠前的那一個。

輸入格式

輸入只有一行，為字串 s。

輸出格式

輸出一行，為最長的回文子字串。

限制

• 1 ≤ |s| ≤ 1000
• s 只包含英文小寫字母

範例

範例 1

輸入

babad

輸出

bab

範例 2

輸入

cbbd

輸出

bb

說明

• 範例 1 中 aba 的長度也是 3，但 bab 的起點較前，所以輸出 bab。
• 範例 2 中最長的回文子字串是 bb。