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

题目描述

给定一个包含大小写字母的字符串 s，你可以通过重新排列这些字母来构造一个最长的回文串。你需要返回这个最长回文串的长度。

注意：

• 回文串是正着读和反着读都一样的字符串。
• 构造时不需要使用所有字符，但只能使用给定的字符。
• 字符串 s 只包含大小写字母，长度范围是 [1, 2000]。

示例 1：
输入: s = "abccccdd"
输出: 7
解释: 最长回文串可以是 "dccaccd"（或 "dccbccd" 等），长度为 7。

示例 2：
输入: s = "a"
输出: 1
解释: 最长回文串是 "a"。

解题思路详解

要构造最长回文串，关键是理解回文串的结构特性。一个回文串可以分为两部分：中心部分和对称部分。

• 对称部分：字符成对出现（例如 "aa" 在两侧），数量可以是任意偶数。
• 中心部分：在回文串正中心，可以有一个单独的字符（如果可用），这是回文串长度可以为奇数的原因。

因此，解题的核心是统计每个字符的出现次数，然后决定哪些字符可以成对使用，以及中心是否可以放一个单独的字符。

解题步骤

我们将通过一个例子 s = "abccccdd" 来逐步说明。

步骤1：统计字符频率

我们需要知道每个字符出现了多少次。由于 s 只包含大小写字母，我们可以用哈希表来记录频率。
遍历 s 的每个字符：

• 遇到字符，在哈希表中增加计数。

对于 s = "abccccdd"：

• 字符频率：a:1, b:1, c:4, d:2。

哈希表（可用字典或长度为 256 的数组）：

• 初始化：freq = {}。
• 遍历 s：
  • 'a' -> freq['a'] = 1
  • 'b' -> freq['b'] = 1
  • 'c' -> freq['c'] = 4
  • 'c' -> freq['c'] = 5（实际是连续4个c，这里逐步加）
  • 'd' -> freq['d'] = 2

最终频率：a:1, b:1, c:4, d:2。

步骤2：计算可用的成对字符数

回文串的对称部分需要字符成对出现。
对于每个字符，其可用的对数为 freq[ch] // 2（整数除法）。
每对字符可以为回文串长度贡献 2。

遍历频率表：

• a: 1 // 2 = 0 对
• b: 1 // 2 = 0 对
• c: 4 // 2 = 2 对 -> 贡献长度 4
• d: 2 // 2 = 1 对 -> 贡献长度 2

当前总长度贡献 = 4 + 2 = 6。

步骤3：检查是否可以添加一个中心字符

如果任何字符有剩余（即出现次数是奇数），我们可以取一个字符放在中心，使回文串长度增加 1。
注意：中心只能放一个字符，即使多个字符有剩余，也只能用一个。

检查每个字符的奇偶性：

• a: 1（奇数）-> 有剩余
• b: 1（奇数）-> 有剩余
• c: 4（偶数）-> 无剩余
• d: 2（偶数）-> 无剩余

存在奇数频率字符（a 或 b），所以可以添加一个中心字符。
总长度 = 对称部分长度 + 1 = 6 + 1 = 7。

步骤4：整合算法

我们可以遍历一次字符串统计频率，然后再遍历频率表（或直接在统计时处理）来累加成对字符数和检查奇数标志。

伪代码：

初始化：length = 0, hasOdd = False
创建一个数组或字典 freq 记录每个字符出现次数
遍历字符串 s 的每个字符 ch：
    freq[ch] += 1
遍历 freq 中的每个计数 count：
    length += (count // 2) * 2
    if count % 2 == 1:
        hasOdd = True
如果 hasOdd 为 True：
    length += 1
返回 length

步骤5：优化空间和时间

我们可以一次遍历同时累加长度和标记奇数。
思路：使用一个集合（哈希集合）来跟踪出现奇数次的字符。

• 遍历每个字符，如果它不在集合中，就加入集合（表示出现奇数次）；如果已在集合中，就移除（表示出现偶数次）。
• 遍历结束后，集合中剩下的字符就是出现奇数次的字符。
• 对称部分长度 = 总字符数 - 集合大小 + 是否用中心。

更直接的算法：

oddSet = set()
for ch in s:
    if ch in oddSet:
        oddSet.remove(ch)
    else:
        oddSet.add(ch)
if len(oddSet) > 0:
    return len(s) - len(oddSet) + 1
else:
    return len(s)

解释：

• 每次字符成对出现时，会从集合中移除，因此集合中保存的是出现奇数次的字符。
• 最长回文串长度 = 总字符数 - 奇数字符数 + 1（如果奇数字符数 > 0，可以选一个放中心）。
• 如果奇数字符数 = 0，则全部字符都可以成对使用，长度就是总字符数。

示例 s = "abccccdd"：

• 总字符数 = 8。
• 遍历后 oddSet = {'a', 'b'}（因为 c 和 d 都成对移除了）。
• len(oddSet) = 2。
• 长度 = 8 - 2 + 1 = 7。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串长度，只需遍历字符串一次。
• 空间复杂度：O(1)，因为字符集大小是常数（最多 52 个大小写字母，集合大小有限）。

扩展思考

• 如果题目要求输出一个具体的最长回文串（而不仅仅是长度），可以在统计频率后，构造前半部分和中心，然后反向得到完整回文串。
• 这题是哈希表在计数问题中的经典应用，通过统计频率来利用回文串的对称性质。