5 Longest Palindromic Substring

class Solution {
public:
    string even(string s, int i) {
        int n = s.size(), j = 0;
        while ( i-j >= 0 and i+j <= n-1 ) {
            if ( s[i-j] != s[i+j] ) return s.substr(i-j+1, 2*j-1);
            j += 1;
        }
        return s.substr(i-j+1, 2*j-1);
    }
    string odd(string s, int i) {
        int n = s.size(), j = 0;
        if ( i == n-1 ) return "";
        while ( i-j >= 0 and i+j+1 <= n-1 ) {
            if ( s[i-j] != s[i+j+1] ) return s.substr(i-j+1, 2*j);
            j += 1;
        }
        return s.substr(i-j+1, 2*j);
    }
    string longestPalindrome(string s) {
        int n = s.size();
        string result = "";
        for ( int i = 0; i <= n-1; i++ ) {
            string e = even(s, i), o = odd(s, i);
            if ( e.size() > result.size() ) result = e;
            if ( o.size() > result.size() ) result = o;
        }
        return result;
    }
};

Use a matrix to record whether s[i:j-i+1] is palindrome.

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        string res;
        bool isPal[1000][1000] = {false};
        int max_len = 0;
        for ( int i = n-1; i >= 0; i-- ) {
            for ( int j = i; j <= n-1; j++ ) {
                if ( ( j-i <= 2 or isPal[i+1][j-1]) and s[i] == s[j] ) {
                    isPal[i][j] = true;
                    if ( j-i+1 > max_len ) { max_len = j-i+1; res = s.substr(i, j-i+1);}
                }
            }
        }
        return res;
    }
};

Notes
In this case, if we use

vector<vector<bool>> isPall(n, vector<bool>(n, false))

we will have time limit exceeds problem. Instead we use 2D array:

bool isPal[1000][1000] = {false};