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
28
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

// dp[i][j] = dp[i + 1][j - 1]

string ans = "";
int idx = 0;
int m = 0;
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (s[i] == s[j]) {
if (i + 1 > j - 1) dp[i][j] = 1;
else dp[i][j] = dp[i + 1][j - 1];
}
if (dp[i][j] && m < j - i + 1) {
m = j - i + 1;
idx = i;
}
}
}

for (int i = idx; i <= idx + m - 1; i++) ans += s[i];
return ans;
}
};