哈希算法题目：最长回文串

题目描述
给定一个包含大写字母和小写字母的字符串 s，返回可以通过这些字母构建的最长回文串的长度。需要注意的是，区分大小写，例如 "Aa" 在这里不视为相同的字符。
示例：
输入: s = "abccccdd"
输出: 7
解释: 最长回文串为 "dccaccd"（或 "dccbccd" 等），长度为 7。

解题过程

1. 理解回文串的字符构成规律

   • 回文串是正读反读都相同的字符串，其字符分布具有对称性。
   • 若回文串长度为偶数，所有字符出现次数均为偶数。
   • 若长度为奇数，除中心字符出现奇数次外，其余字符均出现偶数次。
   • 因此，问题转化为：统计字符串中各字符的出现频次，利用偶数次字符，并最多允许一个奇数次字符作为中心。

2. 统计字符频次

   • 使用哈希表（如字典）记录每个字符的出现次数。
   • 遍历字符串 s，对每个字符 c 执行 hashmap[c] += 1。
   • 示例 s = "abccccdd" 的统计结果：
     a:1, b:1, c:4, d:2

3. 计算有效长度

   • 遍历哈希表，对每个字符的频次 count：
     • 若 count 为偶数，直接全部加入长度（length += count）。
     • 若 count 为奇数，则最多使用 count - 1 个（偶数个）加入长度，并标记“存在奇数次字符”。
   • 最终若存在任何奇数次字符，可额外将其中一个作为中心，总长度 +1。

4. 具体步骤分解

   • 初始化长度 length = 0，标志位 has_odd = False。
   • 统计频次：a:1, b:1, c:4, d:2。
   • 处理 a：count=1（奇数），加入长度 0（因 1-1=0），标记 has_odd = True。
   • 处理 b：count=1（奇数），加入长度 0，保持 has_odd = True。
   • 处理 c：count=4（偶数），加入长度 4。
   • 处理 d：count=2（偶数），加入长度 2。
   • 当前总长度 = 0 + 0 + 4 + 2 = 6。
   • 因存在奇数次字符（a 或 b），总长度可 +1，结果为 7。

5. 算法优化

   • 无需显式区分偶数和奇数：对每个 count，直接加入 count // 2 * 2（即向下取整到偶数）。
   • 若最终长度小于原字符串长度（说明有剩余奇数字符），可额外 +1。
   • 示例中：
     a:1 → 贡献 0，b:1 → 贡献 0，c:4 → 贡献 4，d:2 → 贡献 2，总长 6 < 原长 8，故 +1 得 7。

6. 复杂度分析

   • 时间复杂度 O(n)：遍历字符串统计频次，遍历哈希表计算长度。
   • 空间复杂度 O(1)：字符集大小固定（如字母表最多 52 个字符）。