如何降低最长回文子串查找代码的O(n²)时间复杂度以提升执行效率？

你的代码逻辑是枚举所有可能的子串，再通过反转字符串判断是否为回文，虽然能得到正确结果，但实际时间复杂度是O(n³)（并非你认为的O(n²)）——每个子串的回文判断要花费和子串长度成正比的时间，这才是执行缓慢的核心原因。

下面提供两种高效优化方案：

方案一：中心扩展法（O(n²)时间，常数极小） #

回文的核心特性是对称，我们可以针对每个可能的回文中心（共2n-1个：n个单字符中心，n-1个双字符间隙中心），向左右扩展直到两边字符不相等，记录每次扩展得到的最长回文串。这种方法无需生成子串或反转，仅通过字符比较实现，执行效率远高于原代码。

String longestPalindrome(String s) {
    if (s == null || s.length() == 0) {
        return "";
    }
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        // 处理奇数长度的回文
        int len1 = expandAroundCenter(s, i, i);
        // 处理偶数长度的回文
        int len2 = expandAroundCenter(s, i, i + 1);
        int maxLen = Math.max(len1, len2);
        if (maxLen > end - start) {
            start = i - (maxLen - 1) / 2;
            end = i + maxLen / 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++;
    }
    // 退出循环时左右已不相等，实际回文长度为 right - left - 1
    return right - left - 1;
}

方案二：Manacher算法（O(n)线性时间，最优解） #

如果需要极致效率，Manacher算法可以将时间复杂度降至线性。它利用回文的对称性，通过维护当前最右回文边界和对应中心，跳过重复计算，用数组记录每个位置的最长回文半径。

String longestPalindrome(String s) {
    if (s == null || s.length() == 0) {
        return "";
    }
    // 预处理字符串，插入#统一奇偶长度回文的处理逻辑
    StringBuilder sb = new StringBuilder();
    sb.append('#');
    for (char c : s.toCharArray()) {
        sb.append(c).append('#');
    }
    String t = sb.toString();
    int[] p = new int[t.length()]; // p[i]表示以t[i]为中心的最长回文半径
    int center = 0, right = 0;
    int maxLen = 0, startIdx = 0;

    for (int i = 0; i < t.length(); i++) {
        // 利用对称性初始化当前回文半径
        if (i < right) {
            p[i] = Math.min(right - i, p[2 * center - i]);
        }
        // 尝试向两侧扩展
        int left = i - (p[i] + 1);
        int rightExt = i + (p[i] + 1);
        while (left >= 0 && rightExt < t.length() && t.charAt(left) == t.charAt(rightExt)) {
            p[i]++;
            left--;
            rightExt++;
        }
        // 更新最右回文边界和对应中心
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
        // 更新最长回文的起始位置和长度
        if (p[i] > maxLen) {
            maxLen = p[i];
            startIdx = (i - maxLen) / 2; // 转换回原字符串的起始索引
        }
    }
    return s.substring(startIdx, startIdx + maxLen);
}

另外提一句：你的原代码存在笔误——方法参数是s，但代码中使用了未定义的str，修正后才能正常编译运行。

内容的提问来源于stack exchange，提问作者jaquen v