5

O(n^2) solution

class Solution {
public:
    string longestPalindrome(string s) {
        int len=0, start=0, maxLen;
        for(int i=0; i<s.length(); i++){
            int len1 = findLen(s, i, i);
            int len2 = findLen(s, i, i+1);
            len = max(len1, len2);
            if(len > maxLen){
                maxLen = len;
                start = i-(len-1)/2;
            }
        }
        return s.substr(start, maxLen);
    }

    int findLen(string s, int left, int right){
        while(left>=0 && right < s.length() && s[left] == s[right]){
            left--; right++;
        }
        return right-left-1;
    }
};

---------------------
O(n^2) solution

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        vector<vector<int>> dp(n+2, vector<int>(n+2));

        // Single char are palindrome.
        for(int i=1; i<=n; i++)
            dp[i][i] = 1;

        // Palindromes of length 2.
        for(int i=1; i<n; i++)
            if(s[i-1] == s[i])
                dp[i][i+1] = 1;

        // MCM logic...
        int maxLen = 0, start=0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n-i+1; j++){
                int k = j+i-1;
                if(s[j-1] == s[k-1] && dp[j+1][k-1])
                    dp[j][k] = 1;
                if(dp[j][k] && k-j+1>maxLen){
                    maxLen = k-j+1;
                    start = j-1;
                }
            }
        }
        return s.substr(start, maxLen);
    }
};

-----------------
O(n) solution.

class Solution {
public:
    string longestPalindrome(string s1) {
        int n = s1.length();
        string s="#";
        for(int i=0; i<n; i++){
            s += s1[i];
            s += "#";
        }

        n = s.length();
        vector<int> d1(n);
        int maxLen = 0, start=0;
        for(int i = 0, l = 0, r = -1; i < n; i++) {
            int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
            while(0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
                k++;
            }
            d1[i] = k--;
            if(i + k > r) {
                l = i - k;
                r = i + k;
            }
            if(d1[i] > maxLen){
                maxLen = d1[i];
                start = i-d1[i]+1;
            }
        }
        string ans = "";
        for(int i=start; i<start+2*maxLen-1; i++)
            if(s[i] != '#')
                ans += s[i];
        return ans;
    }
};