算法--最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串

示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：

输入：s = “cbbd”
输出：“bb”

看似困难，实则一点也不简单

方法：中心扩展法（Expand Around Center）

思路：
回文字符串具有对称性，因此我们可以以每个字符为中心，向两边扩展，找到最长的回文子串。需要注意的是，回文可能是奇数长度或偶数长度。

步骤：

1. 遍历字符串中的每个字符。
2. 对于每个字符，分别以奇数长度和偶数长度为中心进行扩展。
3. 记录最长的回文子串。

func longestPalindrome(s string) string {
    if len(s) == 0 {
        return ""
    }
    var maxLen int 
    var start int 
    for i:=0;i<len(s);i++{
        //奇数长度的回文
        l,r := i,i 
        for l>=0 && r<len(s) && s[l] == s[r] {
            if r-l+1>maxLen {
                maxLen = r-l+1
                start = l 
            }
            l--
            r++
        }
        // 偶数长度的回文
        l,r = i,i+1
        for l>= 0 && r < len(s) && s[l] == s[r] {
            if r-l+1 > maxLen {
                maxLen = r-l+1
                start =l 
            }
            l--
            r++
        }
    }
    return s[start:start+maxLen]
}

解释：

• 首先检查字符串是否为空，如果是则返回空字符串。
• 初始化 maxLen 为最大回文长度，start 为最长回文子串的起始位置。
• 遍历字符串中的每个字符 i。
  • 对于奇数长度的回文，以 i 为中心向两边扩展。
  • 对于偶数长度的回文，以 i 和 i+1 为中心向两边扩展。
• 在每次扩展中，如果当前回文长度大于 maxLen，则更新 maxLen 和 start。
• 最后返回最长回文子串。