O(n*n) Time and O(n) Space, LPS based solution (the thing that's used in KMP algorithm) ;)


#1
string Solution::longestPalindrome(string s) {
    int m = s.size();
    string ans = "";
    for (int k = 0; k < m; k++) {
        string a = s.substr(k);
        string temp = a;
        reverse(temp.begin(), temp.end());
        a = a + '~' + temp;
        int n = a.size();
        vector<int> lps(n);
        lps[0] = 0;
        int i = 0, j = 1;
        while (j < n) {
            if (a[i] == a[j]) {
                lps[j] = i + 1;
                i++;
                j++;
            } else {
                if (i == 0) {
                    lps[j++] = 0;
                } else {
                    i = lps[i - 1];
                }
            }
        }
        int len = lps[n - 1];
        if (len > ans.size()) {
            ans = a.substr(0, len);
        }
    }
    return ans;
}

#2

Do you have any proof of correctness on why it works??