摘要

在字符串题里，“回文串”一直是经典题型之一。
这次我们要解决的问题是：给定一串字母，怎么用它们重新排列，拼出能构成的最长回文串？

比如输入 "abccccdd"，我们可以拼出 "dccaccd"，长度为 7。
你可能第一反应是：这题要不要用中心扩展法？或者动态规划？
其实——都不用！

我们只需要数一数每个字母出现了多少次，结果就能直接算出来。
这是一道用统计思路解决字符串构造问题的经典题，非常适合打磨算法直觉。

描述

题目要求：

给定一个由大小写字母组成的字符串 s，请返回通过这些字母能够构造出的 最长回文串的长度。

要点有两个：

1. 区分大小写，比如 "Aa" 不是回文；
2. 不要求返回具体的回文串，只要长度。

题解答案

想象一下回文的结构：
它是左右对称的，也就是说，大部分字母都是成对出现的，
只有中间最多可以有一个“单独的字母”（比如奇数长度的回文中间那个字母）。

比如：

a a b b c c c

我们可以组成 "abccba"（中间放一个单独的字母），
长度 = 成对的字母数 * 2 + 1。

所以我们的思路其实很简单：

1. 统计每个字符出现的次数；
2. 把所有偶数次数都加进结果；
3. 把所有奇数次数 - 1 也加进结果（因为能取成对部分）；
4. 如果有至少一个奇数次数的字符，可以再加 1（放在中间）。

题解代码分析

我们用 Swift 来实现这个逻辑，非常直观。

import Foundation

class Solution {
    func longestPalindrome(_ s: String) -> Int {
        var count: [Character: Int] = [:]
        
        // 1. 统计每个字符出现次数
        for ch in s {
            count[ch, default: 0] += 1
        }
        
        var length = 0
        var hasOdd = false
        
        // 2. 遍历每个字符的次数
        for val in count.values {
            if val % 2 == 0 {
                // 偶数部分全部可以用
                length += val
            } else {
                // 奇数部分只能取 (val - 1)
                length += val - 1
                hasOdd = true
            }
        }
        
        // 3. 如果有奇数出现过，可以在中心加一个字母
        if hasOdd {
            length += 1
        }
        
        return length
    }
}

代码逻辑拆解

这段代码思路非常顺滑：

• 第一步：统计字符出现次数
  用一个字典 count 保存每个字母的数量。Swift 的 default: 用法非常方便，能在不存在的 key 时默认返回 0。

• 第二步：计算能组成的长度
  遍历每个字符的次数：

  • 如果是偶数，全部可以用于对称的两边；
  • 如果是奇数，则只能用 (次数 - 1) 个（留一个放中间的可能性）。

• 第三步：判断中心字母
  如果有至少一个奇数次数的字符（比如 'c' 出现了 3 次），我们可以把其中一个字母放在回文串的中心位置。

示例测试及结果

我们来运行几个例子看看结果：

let solution = Solution()

print(solution.longestPalindrome("abccccdd")) // 输出: 7
print(solution.longestPalindrome("a"))        // 输出: 1
print(solution.longestPalindrome("Aa"))       // 输出: 1
print(solution.longestPalindrome("ccc"))      // 输出: 3
print(solution.longestPalindrome("bananas"))  // 输出: 5 ("anana")

输出结果如下：

7
1
1
3
5

完全符合预期。

时间复杂度

整段逻辑只遍历了字符串一次统计频率，
再遍历一次字典的字符数（最多 52 个字符，大写 + 小写），
因此整体时间复杂度是：

O(n)，其中 n 是字符串长度。

空间复杂度

我们用了一个字典来统计字符次数，
最多存储 52 个字母的统计量，
因此空间复杂度是：

O(1)（常数级，尽管形式上是 O(k)，但 k=52 是固定的）。

总结

这道题非常经典，是“回文构造问题”的入门题。
很多人第一次做会想到动态规划或者双指针，但其实核心是 “字符统计 + 奇偶判断”。

我们总结几个关键点：

1. 不要陷入构造回文串的细节 —— 只要关心计数。
2. 奇偶判断决定能否成对出现。
3. 只要有奇数次字符，就能在中心多放一个。

实际开发类比

这种“统计匹配性”的逻辑，在工程中也非常常见。

比如：

• 检查用户密码的字符配比；
• 计算对称图案中可用的元素数量；
• 游戏中某种“配对”机制（成对组合、剩余元素作为特殊奖励）。

这题看似算法题，但它的思维方式就是 “统计 + 规则映射”，这在数据校验、配置验证、字符串处理里都非常实用。