分析

• 本题的考点：字符串。

• 本题可以使用动态规划解决，时间复杂度是$O(n^2)$，但是理解比较麻烦。这里提供一种时间复杂度相同但是跟容易理解的做法：中心扩散法。

• 我们依次枚举字符串中的每个字母s[i]，然后让s[i]或者(s[i], s[i+1])为中心，向两边扩展，得到以该中心为回文串的大小，记录长度最大的回文串的起点和长度。

代码

• C++

class Solution {
public:
    string longestPalindrome(string s) {

        int start = 0, len = 1;  // 回文串的起点和长度
        for (int i = 0; i < s.size(); i++) {
            int curL = max(expand(s, i, i), expand(s, i, i + 1));
            if (curL > len) {
                len = curL;
                start = i - (curL - 1) / 2;
            }
        }
        return s.substr(start, len);
    }

    int expand(string s, int i, int j) {

        while (i >= 0 && j < s.size()) {
            if (s[i] != s[j]) break;
            i--, j++;
        }
        return j - i - 1;
    }
};

• Java

class Solution {
    public String longestPalindrome(String s) {

        char[] cs = s.toCharArray();

        int start = 0, len = 1;  // 回文串的起点和长度
        for (int i = 0; i < cs.length; i++) {
            int curL = Math.max(expand(cs, i, i), expand(cs, i, i + 1));
            if (curL > len) {
                len = curL;
                start = i - (curL - 1) / 2;
            }
        }
        return s.substring(start, start + len);
    }

    private int expand(char[] s, int i, int j) {

        while (i >= 0 && j < s.length) {
            if (s[i] != s[j]) break;
            i--; j++;
        }
        return j - i - 1;
    }
}

时空复杂度分析

• 时间复杂度：$O(n^2)$，n为字符串长度。

• 空间复杂度：$O(1)$。