HackerRank回文子串计数程序未通过测试用例，求排查可能测试用例

嘿，你的代码在小测试用例里跑的没问题，但遇到长度接近5000的大字符串时肯定会超时——这就是最后两个测试用例失败的核心原因，咱们来一步步捋清楚：

你的代码为什么过不了大测试用例？ #

你现在的思路是先生成所有可能的子串，再反转每个子串对比是否相等。这个方法的时间复杂度是O(n³)：

• 生成所有子串需要O(n²)次循环，每个子串的长度平均是O(n)，光生成子串就已经是O(n³)的开销
• 再给每个子串做反转操作，又是额外的O(n)开销，叠加起来计算量直接爆炸

当字符串长度n=5000时，5000³等于1250亿次操作，这远远超出了平台的时间限制，自然跑不完大测试用例。

更高效的解法：中心扩展法 #

我们可以用中心扩展法把时间复杂度降到O(n²)，这在n=5000时完全可行（总共2500万次操作，平台肯定能接受）。核心思路是：
回文串只有两种类型：

• 奇数长度：中心是单个字符（比如aba的中心是中间的b）
• 偶数长度：中心是两个相邻的相同字符（比如abba的中心是中间的两个b）

我们遍历每个可能的中心，向左右扩展，只要左右字符相等，就计数加1。实现代码如下：

def countPalindromes(s):
    counter = 0
    n = len(s)
    # 处理奇数长度的回文子串
    for i in range(n):
        left, right = i, i
        while left >= 0 and right < n and s[left] == s[right]:
            counter += 1
            left -= 1
            right += 1
    # 处理偶数长度的回文子串
    for i in range(n - 1):
        left, right = i, i + 1
        while left >= 0 and right < n and s[left] == s[right]:
            counter += 1
            left -= 1
            right += 1
    return counter

验证一下你的测试用例 #

• 输入aaa：这个方法会算出6，和你预期的一致（3个单字符、2个双字符、1个三字符）
• 输入abccba：结果是9，完全符合你的预期
• 输入daata：结果是7，也没问题

为什么这个方法更快？ #

总共只有2n-1个可能的中心（n个奇数中心，n-1个偶数中心），每个中心最多扩展O(n)次，总时间复杂度是O(n²)，比你的原方法快了整整一个数量级，完全能应对最大长度的测试用例。

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