Longest Palindromic Substring 是一道非常经典的字符串题。
题目要求我们在一个字符串 s 中，找到最长的回文子串，并把这个子串返回出来。
所谓回文串，就是正着读和反着读都一样的字符串，例如：
-
"aba" -
"abba" -
"racecar"
这道题有很多解法，比如：
-
暴力枚举
-
-
中心扩展法
-
Manacher 算法
本文采用的是最常见、也最容易理解的一种方法：
中心扩展法
这种写法思路清晰，代码简洁，非常适合作为这道题的主流题解。
题目示例
输入：s = "babad"
输出："bab"
或者返回：
"aba"
因为 "bab" 和 "aba" 都是合法答案。
再看一个例子：
输入：s = "cbbd"
输出："bb"
解题思路
回文串有一个非常重要的性质：
它一定是围绕某个“中心”对称的。
例如：
-
"aba"的中心是字符'b' -
"abba"的中心是中间两个字符之间的位置
所以我们可以枚举每一个位置，把它当成回文中心，然后向左右两边扩展，看看最长能扩展多远。
这里要注意，回文串分为两种情况：
-
奇数长度回文串 例如
"aba"，中心是一个字符 -
偶数长度回文串 例如
"abba"，中心是两个字符之间
因此，对于每一个位置 i，都需要做两次扩展：
-
以
i为中心扩展：expandAroundCenter(s, i, i) -
以
i和i+1之间为中心扩展：expandAroundCenter(s, i, i + 1)
然后取两者中的最大值即可。
Java 代码（带注释）
class Solution {
public String longestPalindrome(String s) {
// 特殊情况处理：
// 如果字符串为空，或者长度小于 1，直接返回空字符串
if (s == null || s.length() < 1) return "";
// start 和 end 用来记录当前找到的最长回文子串的左右边界
int start = 0, end = 0;
// 枚举每一个位置，把它作为回文中心
for (int i = 0; i < s.length(); i++) {
// 情况 1：以 s[i] 为中心，寻找奇数长度回文串
int len1 = expandAroundCenter(s, i, i);
// 情况 2：以 i 和 i+1 之间为中心，寻找偶数长度回文串
int len2 = expandAroundCenter(s, i, i + 1);
// 取两种情况中的较大值
int len = Math.max(len1, len2);
// 如果当前回文长度大于之前记录的最长长度，就更新边界
if (len > end - start) {
// 计算当前最长回文的左边界
start = i - (len - 1) / 2;
// 计算当前最长回文的右边界
end = i + len / 2;
}
}
// 根据最终记录的左右边界，截取并返回最长回文子串
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
// 只要左右边界没有越界，并且左右字符相等，就继续向两边扩展
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
// 跳出循环时，left 和 right 已经多走了一步
// 因此回文串长度应为 right - left - 1
return right - left - 1;
}
}
代码拆解
这段代码虽然不长，但细节很多。下面分步骤拆开来看。
1. 特殊情况处理
if (s == null || s.length() < 1) return "";
这一步是为了防止空字符串或者空对象导致后面处理出错。
如果字符串本身为空，那么最长回文子串自然也是空字符串。
2. 用 start 和 end 记录答案区间
int start = 0, end = 0;
这里不直接保存答案字符串，而是先保存最长回文子串的左右边界。
这样做的好处是：
-
避免在遍历过程中频繁截取字符串
-
最后只需要调用一次
substring()就能得到结果
3. 枚举每一个中心点
for (int i = 0; i < s.length(); i++)
这里的 i 表示当前枚举到的位置。
每个位置都可能成为一个回文中心，所以需要全部检查一遍。
4. 为什么要扩展两次？
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
因为回文串既可能是奇数长度，也可能是偶数长度。
奇数长度回文
例如：
"aba"
中心是字符 'b'，所以左右起点相同：
expandAroundCenter(s, i, i)
偶数长度回文
例如：
"abba"
中心不是某个字符，而是中间的空隙，所以左右起点不同：
expandAroundCenter(s, i, i + 1)
这就是为什么每个位置都要检查两种情况。
5. 更新最长回文区间
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
这里是整段代码最关键的地方之一。
为什么左边界是：
i - (len - 1) / 2
为什么右边界是：
i + len / 2
因为我们需要同时兼容奇数和偶数长度的回文串。
举例：
情况 1：奇数长度回文 "aba"
-
中心位置
i = 1 -
长度
len = 3
则：
start = 1 - (3 - 1) / 2 = 0
end = 1 + 3 / 2 = 2
得到区间 [0, 2]，正确。
情况 2：偶数长度回文 "abba"
假设当前中心靠左的位置是 i = 1，长度 len = 4
则：
start = 1 - (4 - 1) / 2 = 0
end = 1 + 4 / 2 = 3
得到区间 [0, 3]，也正确。
所以这个公式能够统一处理奇偶两种情况。
6. 中心扩展函数的作用
private int expandAroundCenter(String s, int left, int right)
这个函数做的事情非常明确：
-
从给定中心开始
-
向左右两边扩展
-
直到不能继续扩展为止
-
返回当前回文串的长度
核心代码：
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
只要满足以下三个条件，就继续扩展：
-
左边界没有越界
-
右边界没有越界
-
左右字符相等
7. 为什么返回 right - left - 1？
这一点非常容易写错。
因为 while 循环结束时，left 和 right 已经多走了一步。
也就是说：
-
left已经走到了回文边界外面一格 -
right也已经走到了回文边界外面一格
所以真正的回文长度应该是：
right - left - 1
例如字符串 "aba"：
-
最终
left = -1 -
最终
right = 3
那么长度就是：
3 - (-1) - 1 = 3
刚好正确。
执行过程演示
以字符串：
"babad"
为例。
当 i = 0
-
奇数扩展得到
"b"，长度为1 -
偶数扩展无法形成回文，长度为
0
当前最长回文是 "b"
当 i = 1
-
奇数扩展可以得到
"bab"，长度为3 -
偶数扩展长度较小
更新最长回文为 "bab"
当 i = 2
-
奇数扩展可以得到
"aba"，长度为3
因为 "aba" 长度也为 3，所以答案可能仍然保持 "bab"，也可能更新为 "aba"，这两种都合法。
复杂度分析
时间复杂度
O(n^2)
原因是：
-
外层循环会枚举每一个字符作为中心
-
每次中心扩展在最坏情况下可能扩展到整个字符串长度
因此整体最坏时间复杂度是 O(n^2)。
空间复杂度
O(1)
整个过程中只使用了少量变量，没有额外使用与输入规模相关的数据结构，因此空间复杂度为常数级。
这道题的优点和特点
中心扩展法的优点非常明显：
-
思路自然，容易理解
-
代码简洁
-
不需要额外数组
-
面试中非常常见
-
足够通过大多数测试
当然，它不是这道题最优的理论解法。
如果追求更高效率，还可以学习 Manacher 算法，它可以做到：
O(n)
但对于大多数刷题场景来说，中心扩展法已经非常实用。
总结
这道题最核心的思想只有一句话：
回文串一定是围绕某个中心对称扩展出来的。
理解了这一点，整道题就非常顺理成章了：
-
枚举每个位置作为中心
-
分别处理奇数回文和偶数回文
-
每次扩展后更新最长回文区间
-
最后根据区间返回答案
这也是这道题最经典、最常用的写法。
适合直接发布的结尾
如果你刚开始刷字符串题，我非常推荐把这道题吃透。
因为它能帮助你掌握几个非常重要的能力：
-
如何从题目性质中提炼解题思路
-
如何设计辅助函数简化主逻辑
-
如何统一处理奇数和偶数两种情况
-
如何在遍历中维护当前最优解
把这道题真正理解透之后，再去看动态规划解法或者 Manacher
