最长回文子串

题目链接：最长回文子串

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

方法一：中心扩散

string longestPalindrome(string s) {
    int n = s.size();
    if (n == 0) return "";

    int bestL = 0, bestLen = 1;

    for (int i = 0; i < n; ++i) {
        int l = i - 1, r = i + 1;

        // 吃掉与中心相同的连续字符（处理 "aaaa" 这类）
        while (l >= 0 && s[l] == s[i]) --l;
        while (r < n && s[r] == s[i]) ++r;

        // 再向两边扩展
        while (l >= 0 && r < n && s[l] == s[r]) { --l; ++r; }

        int len = r - l - 1;
        int start = l + 1;
        if (len > bestLen) { bestLen = len; bestL = start; }
    }
    return s.substr(bestL, bestLen);
}

方法一优化

string longestPalindrome(string s) {
    int n = s.size();
    if (n == 0) return "";

    int bestL = 0, bestLen = 1;

    for (int i = 0; i < n; ) {
        int l = i, r = i;
        while (r + 1 < n && s[r + 1] == s[i]) ++r;  // 合并重复中心
        i = r + 1;                                  // 关键：跳到下一段

        // 扩展
        while (l - 1 >= 0 && r + 1 < n && s[l - 1] == s[r + 1]) { --l; ++r; }

        int len = r - l + 1;
        if (len > bestLen) { bestLen = len; bestL = l; }

        // 可选剪枝：如果剩余长度不足以超越 bestLen
        if ((n - i) * 2 + 1 <= bestLen) break;
    }
    return s.substr(bestL, bestLen);
}