classSolution { 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; } };