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

题目描述：

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

回文串是指正着读和反着读都一样的字符串。

示例：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

输入: "cbbd"
输出: "bb"

解题思路：

1.暴力法

暴力法是最简单直接的方法，遍历所有子串，判断是否为回文串，记录最长的回文串。

时间复杂度：O(n^3)

2.中心扩展法

中心扩展法是基于回文串的对称性质，从中心向两边扩展，判断是否为回文串，记录最长的回文串。

时间复杂度：O(n^2)

3.动态规划法

动态规划法是基于回文串的子串也是回文串的性质，利用状态转移方程，记录最长的回文串。

时间复杂度：O(n^2)

4.马拉车算法

马拉车算法是基于回文串的对称性质和回文串的最大半径，利用中心扩展法的思想，减少重复计算，记录最长的回文串。

时间复杂度：O(n)

参考代码：

1.暴力法

class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if (n < 2) return s;
string res = "";
for (int i = ; i < n; i++) {
for (int j = i; j < n; j++) {
int len = j - i + 1;
if (len > res.size() && isPalindrome(s, i, j)) {
res = s.substr(i, len);
}
}
}
return res;
}
bool isPalindrome(string s, int left, int right) {
while (left < right) {
if (s[left] != s[right]) return false;
left++;
right--;
}
return true;
}
};

2.中心扩展法

class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if (n < 2) return s;
string res = "";
for (int i = ; i < n; i++) {
string s1 = palindrome(s, i, i);
string s2 = palindrome(s, i, i + 1);
res = res.size() > s1.size() ? res : s1;
res = res.size() > s2.size() ? res : s2;
}
return res;
}
string palindrome(string s, int left, int right) {
while (left >= && right < s.size() && s[left] == s[right]) {
left--;
right++;
}
return s.substr(left + 1, right - left - 1);
}
};

3.动态规划法

class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if (n < 2) return s;
vector<vector<bool>> dp(n, vector<bool>(n, false));
int start = , maxLen = 1;
for (int i = ; i < n; i++) {
dp[i][i] = true;
}
for (int j = 1; j < n; j++) {
for (int i = ; i < j; i++) {
if (s[i] != s[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
start = i;
}
}
}
return s.substr(start, maxLen);
}
};

4.马拉车算法

class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if (n < 2) return s;
string t = "#";
for (int i = ; i < n; i++) {
t += s[i];
t += "#";
}
n = t.size();
vector<int> p(n, );
int center = , maxRight = , start = , maxLen = 1;
for (int i = ; i < n; i++) {
if (i < maxRight) {
int mirror = 2 * center - i;
p[i] = min(maxRight - i, p[mirror]);
}
int left = i - (p[i] + 1), right = i + (p[i] + 1);
while (left >= && right < n && t[left] == t[right]) {
p[i]++;
left--;
right++;
}
if (i + p[i] > maxRight) {
center = i;
maxRight = i + p[i];
}
if (p[i] > maxLen) {
maxLen = p[i];
start = (i - maxLen) / 2;
}
}
return s.substr(start, maxLen);
}
};