哈希算法题目：回文排列

题目描述
给定一个字符串，判断该字符串的排列是否可以构成一个回文串（即正着读和反着读相同）。
例如：

• 输入: "code"，输出: false
• 输入: "aab"，输出: true（可排列为 "aba"）
• 输入: "carerac"，输出: true（可排列为 "carerac"）

解题思路
一个字符串能排列成回文串的充要条件是：最多只有一个字符的出现次数为奇数，其余字符的出现次数均为偶数。

原因：

• 回文串关于中心对称：
  • 长度为偶数时，所有字符出现次数均为偶数。
  • 长度为奇数时，除中心字符出现奇数次外，其余字符均为偶数次。
• 因此，统计字符频次后，奇数频次的字符数量不能超过 1。

步骤详解

步骤 1：统计字符频次
用一个哈希表（字典）记录每个字符出现的次数。
例如："aab"

• 'a': 2
• 'b': 1

步骤 2：检查奇数频次的字符数量
遍历哈希表中的计数值：

• 如果是偶数，忽略。
• 如果是奇数，计数器 odd_count 加 1。

步骤 3：判断条件
如果 odd_count <= 1，则返回 true，否则返回 false。

示例推导

例 1："code"

• 频次：{'c':1, 'o':1, 'd':1, 'e':1}
• 奇数频次字符数：4
• 结果：false

例 2："aab"

• 频次：{'a':2, 'b':1}
• 奇数频次字符数：1（'b'）
• 结果：true

例 3："carerac"

• 频次：{'c':2, 'a':2, 'r':2, 'e':1}
• 奇数频次字符数：1（'e'）
• 结果：true

优化与细节

• 只需统计奇数频次的数量，无需完整记录频次后再遍历。可以在遍历过程中动态判断：
  • 遇到某字符时，将其在哈希表中的计数加 1。
  • 若加 1 后该计数变为奇数，则 odd_count++；若变为偶数，则 odd_count--。
• 最终判断 odd_count <= 1。

代码实现（Python）

def canPermutePalindrome(s: str) -> bool:
    odd_count = 0
    freq = {}
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1
        if freq[ch] % 2 == 1:
            odd_count += 1
        else:
            odd_count -= 1
    return odd_count <= 1

复杂度分析

• 时间复杂度：O(n)，遍历字符串一次。
• 空间复杂度：O(k)，k 为字符串中不同字符的数量，最坏情况为 O(n)。