1、方法一：暴力破解（新手常用）

核心思路

    寻找两个重复值，依次判断重复值之间的值是否构成回文子串。

***需要注意字符串长度只有1时的返回值以及多个不同值之间的返回回文子串值

class Solution {

public:

    string longestPalindrome(string s) {

        // 向前读、向后读都一样 即首字和末字一致

        // 挨个字符查询下一个字符的位置判断是否是

        int len = s.size();

        int nums = 0;

        int maxnums=0;

        string substrs = "";

        string maxsubstrs = "";

        if (len == 1)

            return s;

        // printf("%d\n", len);

        for (int i = 0; i < len; i++) {

            for (int j = i + 1; j < len; j++) {

                // 判断是否存在重复值

                if (s[i] == s[j]) {

                    // printf("s[i]：%c\n", s[i]);

                    // printf("i=%d\n", i);

                    // printf("s[j]：%c\n", s[j]);

                    // printf("j=%d\n", j);

                    // printf("maxnums=%d\n", maxnums);

                    if (maxnums <= j - i + 1) {

                        substrs = s.substr(i, j - i + 1);

                        // printf("substrs:%s\n",substrs.c_str());

                        // printf("maxsubstrs:%s\n",maxsubstrs.c_str());

                        nums = substrs.size();

                        // printf("nums=%d\n", nums);

                        for (int k = 0; k < nums; k++) {

                            // printf("起始值：%c\n", substrs[k]);

                            // printf("终点值：%c\n", substrs[nums - k - 1]);

                            if (k != nums - k - 1 &&

                                substrs[k] != substrs[nums - k - 1]) {

                                substrs = "";

                                nums = 0;

                            }

                        }

                        if(maxnums<nums)

                        {

                            maxnums=nums;

                            maxsubstrs=substrs;

                        }

                    }

                } else {

                    if (maxsubstrs == "")

                        maxsubstrs = s[0];

                }

            }

        }

        return maxsubstrs;

    }

};

2、方法二：中心扩展法（豆包、Deepseek提供）

核心思路

回文子串的核心是「对称性」，分为两种类型：

1. 奇数长度：中心是单个字符（如 "bab"，中心为 a）。
2. 偶数长度：中心是两个相邻的相同字符（如 "bb"，中心为两个 b 之间的间隙）。

算法核心：遍历字符串中的每一个可能「中心」，从中心向左右两侧扩展，判断字符是否相等，记录最长回文子串。

class Solution {

public:

    string longestPalindrome(string s) {

        // 边界条件：字符串长度为 0 或 1，直接返回原字符串

        if (s.size() <= 1) {

            return s;

        }

        int start = 0;   // 最长回文子串的起始下标

        int max_len = 1; // 最长回文子串的长度（初始为 1，单个字符都是回文）

        // 遍历每个字符，作为中心进行扩展

        for (int i = 0; i < s.size(); ++i) {

            // 情况 1：奇数长度回文，中心为单个字符 i

            int len1 = expandAroundCenter(s, i, i);

            // 情况 2：偶数长度回文，中心为 i 和 i+1

            int len2 = expandAroundCenter(s, i, i + 1);

            // 取两种情况的最大长度

            int current_max_len = max(len1, len2);

            // 更新最长回文子串的起始下标和长度

            if (current_max_len > max_len) {

                max_len = current_max_len;

                // 计算起始下标：分奇数和偶数长度处理（统一公式）

                start = i - (max_len - 1) / 2;

            }

        }

        // 截取最长回文子串（substr(起始下标, 截取长度)）

        return s.substr(start, max_len);

    }

private:

    // 辅助函数：中心扩展，返回回文子串的长度

    int expandAroundCenter(const string& s, int left, int right) {

        // 左右边界不越界，且对应字符相等时，继续扩展

        while (left >= 0 && right < s.size() && s[left] == s[right]) {

            left--;  // 向左扩展

            right++; // 向右扩展

        }

        // 退出循环时，left 和 right 已经不满足条件，实际回文长度为 (right-1) -

        // (left+1) + 1 = right - left - 1

        return right - left - 1;

    }

};

3、方法三：动态规划（豆包、Deepseek提供）

• 核心思路

• 定义 DP 数组：dp[i][j] 表示「子串 s[i...j] 是否为回文子串」（true 是，false 否）。
• 状态转移方程：
  • 当 s[i] == s[j] 时，分两种情况：
    1. 子串长度 ≤ 2（即 j - i + 1 ≤ 2）：dp[i][j] = true（如 "bb"、"a"）。
    2. 子串长度 > 2：dp[i][j] = dp[i+1][j-1]（内部子串 s[i+1...j-1] 是回文，则当前子串也是回文）。
• 初始化：所有长度为 1 的子串 dp[i][i] = true（单个字符必为回文）。
• 遍历顺序：按「子串长度」从小到大遍历（保证求解 dp[i][j] 时，dp[i+1][j-1] 已求解）。

class Solution {

public:

    string longestPalindrome(string s) {

              int n = s.size();

        if (n <= 1) return s;

       

        int start = 0;

        int max_len = 1;

       

        // 步骤 1：初始化 DP 数组（n x n，默认 false）

        vector<vector<bool>> dp(n, vector<bool>(n, false));

       

        // 步骤 2：初始化长度为 1 的子串

        for (int i = 0; i < n; ++i) {

            dp[i][i] = true;

        }

       

        // 步骤 3：遍历子串长度 l（从 2 到 n）

        for (int l = 2; l <= n; ++l) {

            // 步骤 4：遍历起始下标 i，计算结束下标 j

            for (int i = 0; i + l - 1 < n; ++i) {

                int j = i + l - 1;

               

                // 步骤 5：状态转移方程

                if (s[i] == s[j]) {

                    if (l <= 2) {

                        dp[i][j] = true;

                    } else {

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

                    }

                } else {

                    dp[i][j] = false;

                }

               

                // 步骤 6：更新最长回文信息

                if (dp[i][j] && l > max_len) {

                    max_len = l;

                    start = i;

                }

            }

        }

        return s.substr(start, max_len);

    }

};