1、解题思路

  1. 中心扩展法：遍历字符串中的每一个字符，将其作为回文中心。向左右两边扩展，检查是否构成回文。考虑奇数长度（中心为一个字符）和偶数长度（中心为两个字符）的回文子串。
  2. 动态规划：定义 dp[i][j] 表示字符串从 i 到 j 的子串是否是回文。状态转移方程： 如果 A[i] == A[j] 且 dp[i+1][j-1] 为 true，则 dp[i][j] = true。边界条件：单个字符 dp[i][i] = true，两个相同字符 dp[i][i+1] = (A[i] == A[i+1])。
  3. Manacher算法（进阶要求）：线性时间复杂度 O(n)，空间复杂度 O(n)。利用对称性和已知信息来避免重复计算。

2、代码实现

C++
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A string字符串
     * @return int整型
     */
    int getLongestPalindrome(string A) {
        // write code here
        int n = A.size();
        if (n <= 1) {
            return n;
        }
        int max_len = 1;

        for (int i = 0; i < n; ++i) {
            int len1 = expandAroundCenter(A, i, i); // 奇数长度
            int len2 = expandAroundCenter(A, i, i + 1); // 偶数长度
            max_len = max(max_len, max(len1, len2));
        }
        
        return max_len;
    }

  private:
    int expandAroundCenter(const string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            --left;
            ++right;
        }
        return right - left - 1;
    }
};
Java
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */
    public int getLongestPalindrome (String A) {
        // write code here
        if (A == null || A.length() <= 1) return A.length();
        int max_len = 1;
        for (int i = 0; i < A.length(); i++) {
            int len1 = expandAroundCenter(A, i, i);     // 奇数长度
            int len2 = expandAroundCenter(A, i, i + 1); // 偶数长度
            max_len = Math.max(max_len, Math.max(len1, len2));
        }
        return max_len;
    }

    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}
Python
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A string字符串 
# @return int整型
#
class Solution:
    def getLongestPalindrome(self , A: str) -> int:
        # write code here
        if len(A) <= 1:
            return len(A)
        max_len = 1
        for i in range(len(A)):
            len1 = self.expandAroundCenter(A, i, i)      # 奇数长度
            len2 = self.expandAroundCenter(A, i, i + 1)  # 偶数长度
            max_len = max(max_len, max(len1, len2))
        return max_len

    def expandAroundCenter(self, s: str, left: int, right: int) -> int:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1

3、复杂度分析

关键点说明

  1. 中心扩展法： 时间复杂度 O(n²)，空间复杂度 O(1)。适用于题目要求的 O(n²) 时间复杂度和 O(1) 空间复杂度。
  2. 动态规划： 时间复杂度 O(n²)，空间复杂度 O(n²)。适用于需要记录所有子串是否为回文的情况。
  3. Manacher算法： 时间复杂度 O(n)，空间复杂度 O(n)。适用于题目进阶要求的线性时间复杂度。

复杂度分析

  • 中心扩展法： 时间复杂度：O(n²)，因为每个字符最多被访问两次。空间复杂度：O(1)，仅使用常数个额外变量。
  • 动态规划： 时间复杂度：O(n²)，需要填充 n×n 的 dp 表格。空间复杂度：O(n²)，需要存储 dp 表格。
  • Manacher算法： 时间复杂度：O(n)，线性遍历字符串。空间复杂度：O(n)，需要额外的数组存储信息。

进阶思考

  • 如果需要输出最长回文子串本身，可以在扩展过程中记录子串的起始和结束位置。
  • 如果需要处理更长的字符串（如 n ≤ 10^6），应优先选择 Manacher 算法。