036 · Longest Palindrome

algorithm
Published

June 12, 2026

My First Thoughts

这题有些意思，先确认回文结构本质上需要什么。

题目不要求真的构造出回文串，也不关心字符最后怎么排序。那核心就变成一个条件：

回文串里，除了中间最多可以放一个单独字符之外，其他字符都必须成对出现。

所以拿到字符串 s 以后，第一反应还是先计数。先用字典统计每个字符出现几次，然后遍历这个字典：

  • 如果一个字符出现偶数次，就可以全部放进回文串
  • 如果一个字符出现奇数次，并且次数大于 1，就先拿 count - 1 个进去，让它变成能左右配对的偶数
  • 最后再给回文串中间补一个字符

按这个思路，第一版代码大概是这样：

def longestPalindrome(s):
    counts = {}
    total = 0

    for char in s:
        counts[char] = counts.get(char, 0) + 1

    for key in counts:
        if counts[key] % 2 == 0:
            total += counts[key]
        elif counts[key] % 2 == 1 and counts[key] > 1:
            total += counts[key] - 1

    return total + 1

这个思路整体是顺的。真正的关键已经抓到了：回文串需要“成对”的字符，奇数次字符只能先拿掉一个，剩下的偶数部分可以参与左右对称。

Why That Is Not Enough

上面的代码只剩一个边界没有处理：不是每个输入都需要最后 +1。

如果字符串里存在奇数次字符，比如：

s = "abccccdd"

那么 "a" 或 "b" 这种单独剩下的字符，确实可以放在回文串正中间，所以最后可以加 1。

但如果所有字符出现次数本来都是偶数，比如：

s = "aabb"

所有字符都已经可以成对放进回文串了，最长长度就是 4。这时如果无条件 return total + 1，就会返回 5，超过了原字符串长度。

所以问题不在计数思路，而在最后一步：要不要加中间字符，必须看前面有没有遇到过奇数次字符。

Final Idea

保留原来的计数思路，只加一个状态：has_odd。

它表示：

遍历字符次数时，是否见过至少一个奇数次数的字符。

然后规则就很清楚：

  • 偶数次数：全部加入 total
  • 奇数次数：加入 count - 1，同时把 has_odd 记为 True
  • 最后如果 has_odd 是 True，说明可以放一个中心字符，答案再加 1
  • 如果 has_odd 是 False，说明所有字符都已经成对，不需要额外加中心字符

这样就是从原来的 return total + 1，改成“有奇数才加 1”。

Why It Works

回文串的左右两边必须完全对称，所以每种字符如果要放在左右两边，就必须两个两个地使用。

对于出现偶数次的字符，它可以全部被分到左右两边。

对于出现奇数次的字符，比如 5 次，只能先拿 4 个放在左右两边，剩下 1 个不能再配对。不过整个回文串最多允许一个字符放在正中间，所以只要存在任意一个奇数次字符，最后就可以额外加上一个中心位置。

如果有多个奇数次字符，也只能选其中一个放在中心。其他奇数次字符仍然只能贡献 count - 1 个。

如果一个奇数次字符都没有，说明没有剩余的单个字符需要放中间，也不能凭空多加 1。

Code

def longestPalindrome(s):
    counts = {}
    total = 0
    has_odd = False

    for char in s:
        counts[char] = counts.get(char, 0) + 1

    for count in counts.values():
        if count % 2 == 0:
            total += count
        else:
            total += count - 1
            has_odd = True

    if has_odd:
        total += 1

    return total

Complexity

Time \(O(n)\) - n 是 s 的长度；先遍历字符串计数，再遍历字符种类
Space \(O(1)\) - 字符只包含大小写英文字母，最多保存固定数量的字符计数

Takeaway

当题目里有“最多一个”这种条件时，不要无条件把这个位置加进答案。先用一个状态记住它是否真的存在，再在最后决定要不要补上这一位。

← Quiz