5. 最长回文子串

给你一个字符串 s，找到 s 中最长的 回文 子串。

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：
输入：s = "cbbd"
输出："bb"

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size(), longest = 0, startIndex = 0;
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (s[i] == s[j] &&
                    (i == j || i + 1 == j || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    if (j - i + 1 > longest) {
                        longest = j - i + 1;
                        startIndex = i;
                    }
                }
            }
        }
        return s.substr(startIndex, longest);
    }
};