问题抽象

输出最长回文子串

算法：暴力枚举中点

关键点在于想到要分奇偶情况

复杂度

$O(N^2)$

代码

class Solution {
public:
    string longestPalindrome(string s) {
        int ans = 0;
        string res;
        for(int i = 0; i < s.size(); i ++){
            for(int j = i, k = i; j >= 0 && k < s.size(); j --, k ++){
                if(s[j] != s[k]) break;
                if(ans < k - j + 1){
                    ans = k - j + 1;
                    res = s.substr(j, k - j + 1);
                }
            }

            for(int j = i, k = i+1; j >= 0 && k < s.size(); j --, k ++){
                if(s[j] != s[k]) break;
                if(ans < k - j + 1){
                    ans = k - j + 1;
                    res = s.substr(j, k - j + 1);
                }
            }
        }
        return res;
    }
};

扩展

回文子串