class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        int maxLen = 1, pos = 0;
        vector<vector<bool>> f(n, vector<bool>(n));
        for (int len = 1; len <= n; len ++) {
            for (int i = 0; i + len - 1 < n; i ++) {
                int j = i + len - 1;
                // update --> dp[i][j]
                if (s[i] == s[j]) {
                    if (len <= 2) {
                        f[i][j] = true;
                    } else {
                        f[i][j] = f[i + 1][j - 1];
                    }
                }
                // update --> res: pos, maxLen
                if (f[i][j] && len > maxLen) {
                    maxLen = len;
                    pos = i;
                }
            }
        }
        return s.substr(pos, maxLen);
    }
};

• archive