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

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

示例1：

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

示例2：

输入：s = "cbbd"
输出："bb"

提示：

提示：1 <= s.length <= 1000
s 仅由数字和英文字母组成

c++代码

class Solution {
public:
    string longestPalindrome(string s) {
   int *arr = new int[s.size() * 2 + 2];//存储每个字符对应的回文区间的大小
    arr[0] = 0;
    char *ch=new char[s.size() * 2 + 2];//对应变化后的字符串
    ch[0] = '$';//在字符串开头加上就不会超出左边界
    for (int i = 1; i < s.size() * 2 + 2; i++)
    {
        if (i % 2 == 1)ch[i] = '*';//在每个原来的字符两边加上*
        else ch[i] = s[i / 2 - 1];
    }
    //mx是当前位置的最长回文串的右边界位置
    //en保存的是第一个最大回文串的中心字符
    //id是上一个操作的位置
    int mx, id, en, sum;//sum代表最大的回文字符串的长度
    sum = id = mx = en = 0;//初始化
    for (int i = 1; i < s.size() * 2 + 2; i++)
    {
        if (i < mx)arr[i] = min(mx - i, arr[2 * id - i]);
        else arr[i] = 1;
        while (i + arr[i] < s.size() * 2 + 2 && ch[i - arr[i]] == ch[i + arr[i]])arr[i]++;//判断当前位置的回文的长度
        if (arr[i] + i > mx) {//如果计算出的回文长度对应的边界大于当前存储的边界则更新边界
            mx = arr[i] + i;
            id = i;
            en = sum >= arr[i] ? en : i;//记录最长的回文的中心字符位置
            sum = max(sum, arr[i]);//更新最长回文串的长度
        }
    }
    int h = 1;
    string ns = "";
    for (int j = en - arr[en] + 1; j <= en + arr[en] - 1; j++) {
        if (h % 2 == 0) {//将*舍去
            ns += ch[j];
        }
        h++;
    }
    return ns;
    }
};

Java代码

class Solution {
    public String longestPalindrome(String s) {
        int arr[]=new int[s.length()*2+2];//存储每个字符对应的回文区间的大小
		arr[0]=0;
		char ch[]=new char[s.length()*2+2];//对应变化后的字符串
		ch[0]='$';//在字符串开头加上就不会超出左边界
		for(int i=1;imx) {//如果计算出的回文长度对应的边界大于当前存储的边界则更新边界
				mx=arr[i]+i;
				id=i;
				en=sum>=arr[i]?en:i;//记录最长的回文的中心字符位置
				sum=Math.max(sum, arr[i]);//更新最长回文串的长度
			}
		}
		int h=1;
        String ns="";
		for(int j=en-arr[en]+1;j<=en+arr[en]-1;j++) {
			if(h%2==0) {//将*舍去
                ns+=ch[j];
			}
			h++;
		}
        return ns;
    }
}

思路
使用Manacher（马拉车）算法，求最长回文子串很有用的方法，具体方法讲解可以参考Manacher(马拉车)算法详解。