编程题-最长的回文子串（中等）

题目：

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

示例 1：

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

示例 2：

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

解法一（三重for循环-时间复杂度超限）：

利用滑动窗口思想，遍历字符串s中的所有子串，判断是否是回文子串，并保存最长的回文子串作为输出结果，由于采用三重for循环枚举所有情况，时间复杂度为O(N^3)，时间超限，因此本方法不作为本题的正确解法，仅与下面的方法进行对比，如下为笔者代码：

class Solution {
public:string huiwen(string s, int left, int right){string result = "";int a = left;int b = right;while(left<right){if(s[left]==s[right]){left++;right--;}else{return result;}}for(int i=a; i<b+1; i++){result+=s[i];}return result;}string longestPalindrome(string s) {int length = s.size();int max = 0;string result = "";stack<char> Stack1;for(int i = 0; i<length; i++){int left = i;int right = i;while(right<length){if(s[left]!=s[right]){right++;}else{string a = huiwen(s,left,right);if(max<a.size()){result=a;max=a.size();}right++;}}}return result;}
};

解法二（动态规划思想）：

对于一个子串而言，如果它是回文串，并且长度大于2，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串 “ababa”，如果我们已经知道 “bab”是回文串，那么 "ababa"一定是回文串，这是因为它的首尾两个字母都是"a"。

根据这样的思路，我们就可以用动态规划的方法解决本题。我们用P(i,j)表示字符串s的第i到第j个字母组成的串是否为回文串：

我们就可以写出动态规划的状态转移方程：

上文的所有讨论是建立在子串长度大于 2 的前提之上的，我们还需要考虑动态规划中的边界条件，即子串的长度为 1 或 2。对于长度为 1 的子串，它显然是个回文串；对于长度为 2 的子串，只要它的两个字母相同，它就是一个回文串。因此我们就可以写出动态规划的边界条件：

根据这个思路，我们就可以完成动态规划了，最终的答案即为所有 P(i,j)=true 中 j−i+1（即子串长度）的最大值。注意：在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此一定要注意动态规划的循环顺序，如下为实现代码：

#include <iostream>
#include <string>
#include <vector>using namespace std;class Solution {
public:string longestPalindrome(string s) {int n = s.size();if (n < 2) {return s;}int maxLen = 1;int begin = 0;// dp[i][j] 表示 s[i..j] 是否是回文串vector<vector<int>> dp(n, vector<int>(n));// 初始化：所有长度为 1 的子串都是回文串for (int i = 0; i < n; i++) {dp[i][i] = true;}// 递推开始// 先枚举子串长度for (int L = 2; L <= n; L++) {// 枚举左边界，左边界的上限设置可以宽松一些for (int i = 0; i < n; i++) {// 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得int j = L + i - 1;// 如果右边界越界，就可以退出当前循环if (j >= n) {break;}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];}}// 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置if (dp[i][j] && j - i + 1 > maxLen) {maxLen = j - i + 1;begin = i;}}}return s.substr(begin, maxLen);}
};

时间复杂度：O(n2)，其中 n 是字符串的长度。动态规划的状态总数为 O(n2)，对于每个状态，我们需要转移的时间为 O(1)。空间复杂度：O(n2)，即存储动态规划状态需要的空间。

解法三（中心扩展算法）：

我们仔细观察一下方法一中的状态转移方程：

找出其中的状态转移链：

可以发现，所有的状态在转移的时候的可能性都是唯一的。也就是说，我们可以从每一种边界情况开始「扩展」，也可以得出所有的状态对应的答案。

边界情况即为子串长度为 1 或 2 的情况。我们枚举每一种边界情况，并从对应的子串开始不断地向两边扩展。如果两边的字母相同，我们就可以继续扩展，例如从 P(i+1,j−1) 扩展到 P(i,j)；如果两边的字母不同，我们就可以停止扩展，因为在这之后的子串都不能是回文串了。

「边界情况」对应的子串实际上就是我们「扩展」出的回文串的「回文中心」。方法三的本质即为：我们枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，此时的回文串长度即为此「回文中心」下的最长回文串长度。我们对所有的长度求出最大值，即可得到最终的答案。如下为实现代码：

class Solution {
public:pair<int, int> expandAroundCenter(const string& s, int left, int right) {while (left >= 0 && right < s.size() && s[left] == s[right]) {--left;++right;}return {left + 1, right - 1};}string longestPalindrome(string s) {int start = 0, end = 0;for (int i = 0; i < s.size(); ++i) {auto [left1, right1] = expandAroundCenter(s, i, i);auto [left2, right2] = expandAroundCenter(s, 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);}
};

时间复杂度：O(n2)，其中 n 是字符串的长度。长度为 1 和 2 的回文中心分别有 n 和 n−1 个，每个回文中心最多会向外扩展 O(n) 次。空间复杂度：O(1)。

解法四（Manacher 算法）：

为了表述方便，我们定义一个新概念臂长，表示中心扩展算法向外扩展的长度。如果一个位置的最大回文字符串长度为 2 * length + 1 ，其臂长为 length。

下面的讨论只涉及长度为奇数的回文字符串。长度为偶数的回文字符串我们将会在最后与长度为奇数的情况统一起来。

思路与算法

在中心扩展算法的过程中，我们能够得出每个位置的臂长。那么当我们要得出以下一个位置 i 的臂长时，能不能利用之前得到的信息呢？

答案是肯定的。具体来说，如果位置 j 的臂长为 length，并且有 j + length > i，如下图所示：

当在位置 i 开始进行中心拓展时，我们可以先找到 i 关于 j 的对称点 2 * j - i。那么如果点 2 * j - i 的臂长等于 n，我们就可以知道，点 i 的臂长至少为 min(j + length - i, n)。那么我们就可以直接跳过 i 到 i + min(j + length - i, n) 这部分，从 i + min(j + length - i, n) + 1 开始拓展。

我们只需要在中心扩展法的过程中记录右臂在最右边的回文字符串，将其中心作为 j，在计算过程中就能最大限度地避免重复计算。

那么现在还有一个问题：如何处理长度为偶数的回文字符串呢？

我们可以通过一个特别的操作将奇偶数的情况统一起来：我们向字符串的头尾以及每两个字符中间添加一个特殊字符 #，比如字符串 aaba 处理后会变成 #a#a#b#a#。那么原先长度为偶数的回文字符串 aa 会变成长度为奇数的回文字符串 #a#a#，而长度为奇数的回文字符串 aba 会变成长度仍然为奇数的回文字符串 #a#b#a#，我们就不需要再考虑长度为偶数的回文字符串了。

注意这里的特殊字符不需要是没有出现过的字母，我们可以使用任何一个字符来作为这个特殊字符。这是因为，当我们只考虑长度为奇数的回文字符串时，每次我们比较的两个字符奇偶性一定是相同的，所以原来字符串中的字符不会与插入的特殊字符互相比较，不会因此产生问题。如下为实现代码：

class Solution {
public:int expand(const string& s, int left, int right) {while (left >= 0 && right < s.size() && s[left] == s[right]) {--left;++right;}return (right - left - 2) / 2;}string longestPalindrome(string s) {int start = 0, end = -1;string t = "#";for (char c: s) {t += c;t += '#';}t += '#';s = t;vector<int> arm_len;int right = -1, j = -1;for (int i = 0; i < s.size(); ++i) {int cur_arm_len;if (right >= i) {int i_sym = j * 2 - i;int min_arm_len = min(arm_len[i_sym], right - i);cur_arm_len = expand(s, i - min_arm_len, i + min_arm_len);} else {cur_arm_len = expand(s, i, i);}arm_len.push_back(cur_arm_len);if (i + cur_arm_len > right) {j = i;right = i + cur_arm_len;}if (cur_arm_len * 2 + 1 > end - start) {start = i - cur_arm_len;end = i + cur_arm_len;}}string ans;for (int i = start; i <= end; ++i) {if (s[i] != '#') {ans += s[i];}}return ans;}
};

 时间复杂度：O(n)，其中 n 是字符串的长度。由于对于每个位置，扩展要么从当前的最右侧臂长 right 开始，要么只会进行一步，而 right 最多向前走 O(n) 步，因此算法的复杂度为 O(n)。空间复杂度：O(n)，我们需要 O(n) 的空间记录每个位置的臂长。

笔者小记：

1、vector<vector<int>> dp(n, vector<int>(n));含义，其中vector<vector<int>>定义了一个二维向量（矩阵），它的元素是int类型，外层的vector存储的是内层vector的集合。(n, vector<int>(n))是创建了一个n*n的矩阵，其中每个元素都是int类型的默认值（通常为0），n是矩阵的行数，vector<int>(n)创建了一个大小为n的vector<int>，这个向量会作为外层向量的每一个元素。

2、std::string substr()用于提取字符串的子串，允许指定起始位置和长度，例如

str.substr(7, 5);

表示提取str字符串索引位置从7开始的子串，长度为5。

3、C++中pair的用法：pair 是 一种模版类型。每个pair 可以存储两个值。这两种值无限制。也可以将自己写的struct的对象放进去。例如：pair<string,int> p; pair<int ,int > p; pair<double,int> p; 等都可以，若函数采用pair类型，则可以用return {int, int}进行返回。在函数外，可以采用auto [left1, right1] = expandAroundCenter(s, i, i)进行接受返回的{int, int}。例如：

pair<int, int> expandAroundCenter(const string& s, int left, int right) {while (left >= 0 && right < s.size() && s[left] == s[right]) {--left;++right;}return {left + 1, right - 1};}

auto [left1,right1] 接收expandAroundCenter()函数返回的{left, right}值：

auto [left1, right1] = expandAroundCenter(s, i, i);