5. [✔][M]最长回文子串

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

---

题解：

双指针解决数组问题

使用双指针，从中间向两头移动，判断是否是回文。本题重点是分奇数回文和偶数回文两种情况。

/*
 * @lc app=leetcode.cn id=5 lang=typescript
 *
 * [5] 最长回文子串
 */

// @lc code=start
function longestPalindrome(s: string): string {

    // 关键点是这个从中心到两边的双指针查找法
    const palindrome = (str: string, left: number, right: number): string => {
        while (left >= 0 && right <= str.length - 1 && str[left] === str[right]) {
            left--;
            right++
        }
        // left+1是因为上面循环最后--后退出了，所以有效的回文应该是left+1
        // right在上面循环中也++了，但是还是使用right是因为substring第二个参数是end但是不包含end索引，所以刚好
        return s.substring(left + 1, right)
    }

    let result = "";

    for (let i = 0; i < s.length; i++) {
        let s1 = palindrome(s, i, i);//奇数回文
        let s2: string = palindrome(s, i, i + 1);// 计算i和i+1，也就是偶数的回文也很巧妙
        result = s1.length > result.length ? s1 : result;
        result = s2.length > result.length ? s2 : result;
    }

    return result;

};
// @lc code=end