哈希算法题目：回文排列

题目描述
给定一个字符串，判断该字符串是否可以通过重新排列组合，形成一个回文串（即正着读和反着读都一样的字符串）。例如，输入 "code" 返回 false，因为无法排列成回文；而输入 "aab" 返回 true，因为可以排列成 "aba"。

解题过程

1. 理解回文排列的核心条件

   • 回文串分为奇数长度和偶数长度两种情况：
     • 偶数长度时，每个字符必须出现偶数次（如 "abba"）。
     • 奇数长度时，除一个字符出现奇数次（作为中心字符），其余字符必须出现偶数次（如 "abcba"）。
   • 因此，允许最多一个字符的出现次数为奇数，其余字符出现次数必须为偶数。

2. 选择数据结构记录字符频次

   • 使用哈希表（字典）统计每个字符的出现次数。键为字符，值为出现次数。

3. 遍历字符串并统计频次

   • 示例：字符串 "aab"
     • 初始化空哈希表 count = {}
     • 遍历字符 'a'：count['a'] = 1
     • 遍历字符 'a'：count['a'] = 2
     • 遍历字符 'b'：count['b'] = 1
     • 最终哈希表：{'a': 2, 'b': 1}

4. 检查奇数次字符的数量

   • 遍历哈希表，统计出现次数为奇数的字符个数（即 count[char] % 2 == 1 的字符数量）。
   • 若奇数字符个数为 0 或 1，则满足回文排列条件；否则不满足。
   • 示例 "aab"：奇数字符为 'b'（出现 1 次），个数为 1，返回 true。

5. 优化方案

   • 无需完整统计所有频次，只需用哈希集合记录出现奇数次的字符：
     • 遍历字符时，若字符不在集合中，则加入集合（标记为奇数次）；若已在集合中，则移除（标记为偶数次）。
     • 最终检查集合大小是否 ≤1。
   • 示例 "aab"：
     • 遍历 'a'：集合 {'a'}
     • 遍历 'a'：集合 {}
     • 遍历 'b'：集合 {'b'}
     • 集合大小为 1，返回 true。

总结
通过哈希结构高效统计字符频次，利用回文串的数学特性（奇数字符最多一个），即可在 O(n) 时间复杂度和 O(k) 空间复杂度（k 为字符集大小）内解决问题。