1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> f(n, vector<bool>(n, false));
        string res = s.substr(0, 1);

        for (int i = 0; i < n; i++) {
            f[i][i] = true;
            if (i < n - 1 && s[i] == s[i + 1]) {
                f[i][i + 1] = true;
                res = s.substr(i, 2);
            }
        }

        for (int d = 2; d < n; d++) {          // d = j - i
            for (int i = 0; i + d < n; i++) {
                int j = i + d;
                if (s[i] == s[j] && f[i + 1][j - 1]) {
                    f[i][j] = true;
                    res = s.substr(i, d + 1);  // d increases, so this is always the longest so far
                }
            }
        }
        return res;
    }
};