最长回文子串

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

示例 1：

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

输入：s = “cbbd”
输出：“bb”
示例 3：

输入：s = “a”
输出：“a”
示例 4：

输入：s = “ac”
输出：“a”

class Solution {
public:
    string longestPalindrome(string s)
    {
        int n = s.size();
        constexpr int bound_2 = 2;
        if (n < bound_2) {
            return s;
        }
        vector> dp(n, vector(n)); // dp[i][j]表示s[i..j]是否是回文串
        for (int i = 0; i < n; i++) { // 初始化：所有长度为 1 的子串都是回文串
            dp[i][i] = true;
        }

        int maxLen = 1; // 最长回文子串长度初始值设为1
        int start = 0;
        for (int len = 2; len <= n; len++) { // 子串长度
            for (int left = 0; left < n; left++) { // 枚举左边界，左边界的上限设置可以宽松一些
                int right = left + len - 1; // 右边界
                if (right >= n) {  // 如果右边界越界，就可以退出当前循环
                    break;
                }
                // 转移方程,封装防止嵌套过深
                TransmitProc(s, dp, left, right);

                // 只要 dp[left][right] == true 成立，就表示子串 s[left,right] 是回文，此时记录回文长度和起始位置
                if (dp[left][right] && right - left + 1 > maxLen) {
                    start = left;
                    maxLen = right - left + 1;
                }
            }
        }
        return s.substr(start, maxLen);
    }

    void TransmitProc(string& s, vector>& dp, int left, int right)
    {
        constexpr int bound_3 = 3;
        if (s[left] != s[right]) {
                    dp[left][right] = false;
        } else {
            if (right - left < bound_3) { // 边界的处理
                dp[left][right] = true;
            } else {
                dp[left][right] = dp[left + 1][right - 1];
            }
        }
        return;
    }
};

class Solution {
public:
    string palindrome(string& s, int left, int right)
    {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            --left;
            ++right;
        }
        return s.substr(left + 1, right - left - 1); // 返回以 s[left] 和 s[right] 为中⼼的最⻓回⽂串
    }
    string longestPalindrome(string s) {
        string res;
        for (int i = 0; i < s.size(); i++) {
            string s1 = palindrome(s, i, i); // 以i为中心的回文子串
            string s2 = palindrome(s, i, i + 1); // 以i和i+1为中心的子串
            res = (res.size() > s1.size()) ? res : s1;
            res = (res.size() > s2.size()) ? res : s2;
        }
        return res;
    }
};

C++17尝鲜：结构化绑定声明（Structured Binding Declaration）

class Solution {
public:
    pair palindrome(string& s, int left, int right)
    {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            --left;
            ++right;
        }
        return {left + 1, right - 1}; // 返回以 s[left] 和 s[right] 为中⼼的最⻓回⽂串
    }
    string longestPalindrome(string s) {
        string res;
        int start = 0;
        int end = 0;
        for (int i = 0; i < s.size(); i++) {
            auto [left1, right1] = palindrome(s, i, i); // 以i为中心的回文子串
            auto [left2, right2] = palindrome(s, i, i + 1); // 以i和i+1为中心的子串
            if (right1 - left1 > end - start) {
                start = left1;
                end = right1;
            }
            if (right2 - left2 > end - start) {
                start = left2;
                end = right2;
            }
        }
        return s.substr(start, end - start + 1);
    }
};