同事月薪2万8，上有老下有小，房贷每月1万2。他跟我说:我现在出去面试，人家一看年龄就摇头。

回文你肯定知道吧，就是正着读反着读都一样那种，aba、abba、a。

题目大概就是：给你一个字符串，比如 "babad"，让你在里面找一个最长的回文子串出来。 像 "bab" 和 "aba" 都行，随便返回一个就可以。

重点有两个：

• 必须是连续的子串，不是子序列
• 要最长，不是随便找一个就跑

面试官一般会补一句：字符串长度可能是几千、几万，你可别给我整个 O(n³) 的暴力。

小李第一反应一般都是这种思路： “把所有子串枚举一遍，每个子串再检查是不是回文，取最长的那个。”

听着没问题对吧，伪代码脑补一下：

• 左边界 i 从 0 到 n-1
• 右边界 j 从 i 到 n-1
• 然后再用一个 while 从两边往中间比字符

时间复杂度怎么算呢： 枚举子串是 O(n²)，每个子串再检查一次 O(n)，合起来 O(n³)。 n 如果是 1000，立马炸裂，面试官人都没了。

所以这个思路一般只能当你跟别人说：“我先说个最直观但会超时的做法哈。” 说完赶紧自己把自己否了，再换个版本。

我当时就跟小李说，你别老想着“枚举子串”，你可以换个角度：“枚举回文的中心”。

为啥？因为回文这个东西有个很爽的性质：它是以中点对称的。

你看这几个：

• 奇数长度：aba 以中间的 b 为中心
• 偶数长度：abba 以中间那两个 b 之间缝为中心

所以我们可以干一件事：

1. 枚举每一个“中心位置”
2. 从这个中心往两边扩展，只要两边字符一样就继续扩
3. 扩不动了，这一轮就拿到了一个以它为中心的最长回文

注意中心有两种情况：

• 1 个字符当中心：处理奇数长度，比如 aba
• 2 个字符当中心：处理偶数长度，比如 abba

所以第 i 个位置，要算两次：

• 以 (i, i) 为中心
• 以 (i, i+1) 为中心

每次扩展的那段长度算出来，跟全局的最长做对比，更新一下起始下标就完了。

时间复杂度怎么说呢： 中心有 n 个，每个中心最多向两边扩 n 次，整体就是 O(n²)，面试官一般是能接受的。 空间只用常数几个变量，O(1)。

我抽完最后一口烟，给小李在手机上敲了个最常用的版本，大概就这样：

publicclassLongestPalindrome{

public String longestPalindrome(String s){
if (s == null || s.length() < 2) {
return s;
        }

int start = 0;
int end = 0;

for (int i = 0; i < s.length(); i++) {
// 情况一：奇数长度，以 i 为中心
int len1 = expandFromCenter(s, i, i);
// 情况二：偶数长度，以 i 和 i+1 为中心
int len2 = expandFromCenter(s, i, i + 1);

int len = Math.max(len1, len2);

// 当前找到的比历史最长的还长，就更新一下左右边界
if (len > end - start + 1) {
// 这个推导你可以自己拿纸算一下，很常见的写法
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }

return s.substring(start, end + 1);
    }

// 从 left 和 right 出发，向两边扩展，返回以它们为中心的最长回文长度
privateintexpandFromCenter(String s, int left, int right){
int n = s.length();
while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
// 跳出循环的时候，left 和 right 已经多走了一步，所以要减 1
return right - left - 1;
    }

// 简单测一下
publicstaticvoidmain(String[] args){
        LongestPalindrome solver = new LongestPalindrome();
        System.out.println(solver.longestPalindrome("babad")); // bab 或 aba
        System.out.println(solver.longestPalindrome("cbbd"));  // bb
        System.out.println(solver.longestPalindrome("a"));     // a
        System.out.println(solver.longestPalindrome("ac"));    // a 或 c
    }
}

几个小点随手说下：

• 那两个公式 start = i - (len - 1) / 2 和 end = i + len / 2，其实已经把奇数和偶数长度统一处理掉了，不用单独分类
• expandFromCenter 那个 while 出来以后，要返回 right - left - 1，因为 left/right 都已经越界了一步，这是面试时最容易写错的地方
• 如果字符串本身就很短，比如长度 0 或 1，直接返回就行，别瞎算

那会儿小李还不满足，又问：“那 dp 怎么搞？” 我困得不行就简单跟他讲了一句：

你可以开个二维数组 dp[i][j]，表示子串 s[i..j] 是不是回文。 状态转移大概是：

• 两端字符相等：s[i] == s[j]
• 并且里面那一段也是回文：dp[i+1][j-1] == true
• 或者中间已经“空了”（j - i <= 2），比如 aa、aba 这种直接就是回文

然后 i 从后往前遍历，j 从 i 往后遍历，一边填表一边顺手记录最长长度和起点。 时间 O(n²)，空间 O(n²)，就不写代码了，面试的时候一般中心扩展那个版本够用，也更好写。