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

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

示例 1：

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

示例 2：

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

提示：

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

思路：

方案一：中心扩展算法。
  感觉就是枚举，对每一个字符向两边遍历，获取以该字符为中心的最长回文子串。
  由于回文子串可能是偶数，所以也要遍历 i, i + 1, 向两边扩展的情况。
  时间复杂度 O(n²)

string longestPalindrome(string s) {
    string res = "";
    for (int i = 0; i < s.size(); i++) {
        string res1 = helper(s, i, i);
        string res2 = helper(s, i, i + 1);
        if (res.size() < res1.size())
            res = res1;
        if (res.size() < res2.size())
            res = res2;
    }
    return res;
}
string helper(string &s, int l, int r) {
    while (l >= 0 && r < s.size() && s[l] == s[r]) {
        l--;
        r++;
    }
    return s.substr(l + 1, r - l - 1);
}

方案二：Manacher 算法

  在中心扩展算法的基础上记录了右臂在最右边的回文子串，记录了已经遍历过的字符的回文子串。
  在遍历到新的字符时，根据回文串对称的性质，减少遍历次数。
  用特殊字符进行填充，把偶数回文变成奇数回文
  时间复杂度 O(n)

class Solution {
public:
    int expand(const string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            --left;
            ++right;
        }
        return (right - left - 2) / 2;
    }

    string longestPalindrome(string s) {
        int start = 0, end = -1;
        string t = "#";
        for (char c: s) {
            t += c;
            t += '#';
        }
        t += '#';
        s = t;

        vector<int> arm_len;
        int right = -1, j = -1;
        for (int i = 0; i < s.size(); ++i) {
            int cur_arm_len;
            if (right >= i) {
                int i_sym = j * 2 - i;
                int min_arm_len = min(arm_len[i_sym], right - i);
                cur_arm_len = expand(s, i - min_arm_len, i + min_arm_len);
            } else {
                cur_arm_len = expand(s, i, i);
            }
            arm_len.push_back(cur_arm_len);
            if (i + cur_arm_len > right) {
                j = i;
                right = i + cur_arm_len;
            }
            if (cur_arm_len * 2 + 1 > end - start) {
                start = i - cur_arm_len;
                end = i + cur_arm_len;
            }
        }

        string ans;
        for (int i = start; i <= end; ++i) {
            if (s[i] != '#') {
                ans += s[i];
            }
        }
        return ans;
    }
};

方案三：动态规划

string longestPalindrome(string s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n)); // dp[i][j] 表示 s[i..j] 是否是回文子串
    for (int i = 0; i < n; ++i) {
        dp[i][i] = true; // 初始化，所有长度为1的子串都是回文串
    }

    int len = 1, begin = 0;
    for (int length = 2; length <= n; length++) {
        for (int left = 0; left < n; ++left) {
            int right = left + length - 1;
            if (right >= n)
                break;
            if (s[left] == s[right]) {
                if (right - left == 1) // 长度为 2 的子串
                    dp[left][right] = true;
                else
                    dp[left][right] = dp[left + 1][right - 1];
            }
            if (dp[left][right] && right - left + 1 > len) {
                len = right - left + 1;
                begin = left;
            }
        }
    }
    return s.substr(begin, len);
}

动态规划另一种实现：

string longestPalindrome(string s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n)); // dp[i][j] 表示 s[i..j] 表示的回文子串长度
    for (int i = 0; i < n; ++i) {
        dp[i][i] = 1; // 初始化，所有长度为1的子串都是回文串
    }

    int len = 1, begin = 0;
    for (int i = n - 2; i >= 0; --i) {
        for (int j = i + 1; j < n; ++j) {
            if (s[i] == s[j] && (dp[i + 1][j - 1] != 0 || j - i == 1)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
            }
            if (dp[i][j] > len) {
                len = dp[i][j];
                begin = i;
            }
        }
    }
    return s.substr(begin, len);
}

类似题目:最长回文子序列