哈希算法题目：最长回文串（构造最长回文串）

题目描述
给定一个包含大小写字母的字符串 s，你需要用这些字母构造一个最长的回文串。你可以自由地重新排列这些字母，但构造时必须遵循回文串的对称规则，并且每个字母的使用次数不能超过其在原字符串中出现的次数。返回可以构造的最长回文串的长度。

示例
输入："abccccdd"
输出：7
解释：可以构造的最长回文串之一是 "dccaccd" 或 "dccbccd"，长度为 7。

解题过程详解

1. 理解回文串的构造规则
回文串分为两种形式：

• 奇数长度：中间有一个字符出现奇数次，其余字符成对出现（偶数次）。
• 偶数长度：所有字符都成对出现（偶数次）。

为了构造最长回文串，我们应该尽可能多地使用成对的字符，并最多允许一个字符作为中心（如果存在奇数频率的字符）。

2. 算法步骤拆解

(1) 统计每个字符的出现次数
因为字符串中可能包含大小写字母，我们需要记录每个字符（例如 'a' 到 'z' 和 'A' 到 'Z'）出现的次数。
最直接的方法是使用哈希表（字典）来记录字符频率。

(2) 计算可用的成对字符
对于每个字符：

• 如果出现次数是偶数（例如 4 次），则全部可以用于回文串的两侧。
• 如果出现次数是奇数（例如 5 次），则可以取其中的偶数部分（4 次）用于两侧，剩下的 1 次可能作为中心。

简单计算：
对于每个字符，可用的成对数量 = (次数 // 2) * 2。
例如 5 次 → 可用 4 次（即 2 对）。

(3) 累加成对字符的贡献，并判断是否可以添加一个中心

• 初始化结果长度 length = 0。
• 遍历哈希表中的每个字符频率 count：
  • 将 (count // 2) * 2 加到 length 中。
• 如果某个字符有奇数次的剩余（即 count % 2 == 1），并且当前结果长度是偶数（意味着还没有中心字符），则可以增加 1 作为中心。

3. 举例逐步演示

以 s = "abccccdd" 为例：

(1) 统计频率（哈希表）

a: 1
b: 1
c: 4
d: 2

(2) 遍历并累加成对部分

• a 出现 1 次：(1 // 2) * 2 = 0 → 长度不变（length = 0）。
• b 出现 1 次：(1 // 2) * 2 = 0 → length = 0。
• c 出现 4 次：(4 // 2) * 2 = 4 → length = 4。
• d 出现 2 次：(2 // 2) * 2 = 2 → length = 6。

此时 length = 6，表示已经有 6 个字符成对使用。

(3) 检查是否可以添加中心
当前 length 是偶数（6），表示还没有中心字符。
检查是否有字符有剩余 1 次：

• a 剩余 1 次（奇数）→ 可以加入中心，长度加 1。
• 或者 b 剩余 1 次 → 同样可以，但只需加一次。

最终 length = 7。

对应回文串构造（一种可能）：

• 成对部分：ccc（左侧）和 ccc（右侧）对称，d 和 d 对称。
• 中心部分：加入一个 a 或 b。
  例如："d c c a c c d"（长度为 7）。

4. 算法优化

实际上，可以一次遍历完成计算，无需先建完整哈希表再遍历：

• 用一个集合（Set）来跟踪出现奇数次的字符。
• 遍历字符串每个字符 ch：
  • 如果 ch 在集合中，则移除（表示配对成功），同时将结果长度加 2。
  • 如果不在集合中，则加入集合。
• 遍历结束后：
  • 如果集合非空，说明有未配对的字符，可以选一个作为中心，长度加 1。

举例 s = "abccccdd"：

• 初始：集合 set = {}, length = 0。
• 字符 a：不在集合 → 加入集合 {a}，length = 0。
• 字符 b：不在集合 → 加入 {a, b}，length = 0。
• 字符 c：不在集合 → 加入 {a, b, c}，length = 0。
• 字符 c：在集合 → 移除 c，{a, b}，length = 2。
• 字符 c：不在集合 → 加入 {a, b, c}，length = 2。
• 字符 c：在集合 → 移除 c，{a, b}，length = 4。
• 字符 d：不在集合 → 加入 {a, b, d}，length = 4。
• 字符 d：在集合 → 移除 d，{a, b}，length = 6。
  结束：集合非空（有 a 或 b），可加中心 → length = 7。

这种方法只需要 O(n) 时间，空间 O(k)（k 是字符集大小，最多 52）。

5. 代码实现（Python）

def longestPalindrome(s: str) -> int:
    char_set = set()
    length = 0
    
    for ch in s:
        if ch in char_set:
            char_set.remove(ch)
            length += 2
        else:
            char_set.add(ch)
    
    if char_set:  # 如果还有未配对的字符
        length += 1
    
    return length

测试示例

输入："abccccdd"
输出：7

输入："a"
输出：1

输入："bb"
输出：2

总结
这个问题的核心在于用哈希集合追踪字符的配对状态。每个字符在第一次出现时加入集合，第二次出现时从集合移除并计为 2 个字符（成对使用）。最后如果集合中还有字符，说明可以选一个作为中心。这个算法简洁且高效，时间复杂度 O(n)，空间复杂度 O(字符集大小)。