Problem Description

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

Examples

Example 1:

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

Example 2:

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

Constraints:

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

解析

題目給定一個字串 s, 要找出字串中最長的回文子字串

如果一個字串 s 是回文

代表 字串的字元 存在一個 index i, i = floor(len(s)/2)

使得 s[i+k] == s[i-k] , k = 1 ,… floor(len(s)/2) if len(s) % 2 == 1

    s[i+k] == s[i-k-1], k=0,…len(s)/2 - 1 if len(s)%2 == 0

來思考一下 回文字串組成要件

“aba” 是回文則 “xabax” 也是回文

也就是要形成回文可以從基本字元開始檢查