LeetCode 409：最长回文串 | 哈希表统计字符频率

LeetCode 409最长回文串 | 哈希表统计字符频率引言最长回文串Longest Palindrome是 LeetCode 第 409 题难度为 Easy。题目要求在给定字符串中构造最长的回文串返回其长度。这道题虽然简单但蕴含了回文串构造的核心原理对出现偶数次的字符可以全部放入回文串出现奇数次的字符最多只能取其偶数部分而多余的奇数字符可以放在回文串的中间位置。哈希表在这个问题中用于统计每个字符出现的次数。基于统计结果我们可以计算出最长回文串的长度。这道题的扩展性很强可以推广到构造实际的回文串而不仅仅是计算长度。问题分析题目描述给定一个包含大写字母、小写字母和数字的字符串找到用这些字符能构造的最长回文串的长度。例如输入字符串 abccccdd可以构造的最长回文串是 dccbccd 或 bccdccb 等长度为 7dccbccd。回文串构造原理回文串的特点是左右对称。在构造回文串时对于每个字符如果出现偶数次这个字符可以完整地放在回文串的左右两侧。如果出现奇数次这个字符只能取其偶数部分如 5 次取 4 次多余的 1 次可以放在回文串的中间位置。因此最长回文串的长度计算公式为所有字符的偶数部分之和加上 1如果存在至少一个奇数次的字符用于放在中间更精确地说设每个字符的出现次数为 count_i则回文串的长度为sum(min(count_i, 2 * floor(count_i / 2)))即所有字符的偶数部分之和如果存在至少一个 count_i 为奇数加 1简化为sum(count_i // 2 * 2) (1 if any(count_i % 2 1) else 0)解决方案哈希表统计def longestPalindrome(s: str) - int: char_count {} for char in s: char_count[char] char_count.get(char, 0) 1 length 0 has_odd False for count in char_count.values(): if count % 2 0: length count else: length count - 1 has_odd True if has_odd: length 1 return length这段代码首先使用哈希表统计每个字符的出现次数。然后遍历所有计数累加偶数部分处理奇数部分最后根据是否有奇数以决定是否加 1。使用 Python 的 Counterfrom collections import Counter def longestPalindrome_counter(s: str) - int: count Counter(s) length 0 for c in count.values(): length c // 2 * 2 if length len(s): length 1 return length这个版本更简洁。首先累加每个字符的偶数部分c // 2 * 2。然后如果处理后的长度小于原字符串长度说明存在奇数次的字符可以在中间再加一个字符。优化版本def longestPalindrome_optimized(s: str) - int: odd_count sum(1 for c in set(s) if s.count(c) % 2 1) return len(s) if odd_count 0 else len(s) - odd_count 1这个优化版本利用了一个重要观察回文串的长度等于原字符串长度减去需要去掉的奇数字符数即多余的奇数部分再加上 1如果有奇数字符。具体来说对于每个出现奇数次的字符我们需要去掉 1 个字符如 5 次去掉 1 次剩 4 次需要去掉的总数 奇数字符的出现次数之和 - 奇数字符的种类数但更简单的计算方式是如果有奇数字符总长度 原长度 - 奇数字符种类数 1算法正确性证明关键引理对于任意字符如果其出现次数为 c可以用于构成回文串左半边或右半边的字符数为 floor(c / 2) * 2如果 c 是奇数剩余 1 个字符可用于放在回文串中间构造性证明我们可以构造一个具体的回文串来证明算法的最优性对于每个字符取 floor(c / 2) * 2 个字符将这些字符对半分到回文串的左右两侧。收集所有奇数字符多余的 1 个字符。将步骤 2 收集的字符最多一种如果多种任选一种放在回文串的中间。步骤 1 使用的字符总数就是回文串长度。这个构造证明了算法的上界是可达的因此算法是最优的。代码实现Python 实现def longestPalindrome(s: str) - int: char_count {} for char in s: char_count[char] char_count.get(char, 0) 1 length 0 odd_exists False for count in char_count.values(): if count % 2 0: length count else: length count - 1 odd_exists True if odd_exists: length 1 return lengthJava 实现public int longestPalindrome(String s) { int[] count new int[128]; for (char c : s.toCharArray()) { count[c]; } int length 0; boolean hasOdd false; for (int c : count) { if (c % 2 0) { length c; } else { length c - 1; hasOdd true; } } return hasOdd ? length 1 : length; }Java 实现中使用了固定大小的数组ASCII 字符集大小来代替哈希表可以稍微提升性能。复杂度分析时间复杂度时间复杂度为 O(n)其中 n 是字符串长度。我们需要遍历字符串一次来统计字符频率然后遍历字符集最多 128 或 256 个字符一次来计算长度。空间复杂度空间复杂度为 O(1) 或 O(n)取决于字符集大小。如果使用哈希表空间复杂度为 O(n)最坏情况下所有字符都不同如果使用固定大小的数组空间复杂度为 O(1)。边界情况处理空字符串当输入为空字符串时没有任何字符可以构成回文串应返回 0。代码正确处理了这种情况odd_exists 为 Falselength 为 0。全相同字符当所有字符相同时如 aaaa回文串长度等于字符串长度 4。所有字符都可以用于构成回文串。全不同字符当所有字符都不同时如 abc没有任何字符可以配对只能取一个字符放在中间回文串长度为 1。混合情况如 abccccdd字符频率为 a:1, b:1, c:4, d:2。偶数部分为 426加上 1因为有奇数字符 a 和 b总长度为 7。变种问题构造实际的回文串如果不仅要求长度还要求返回具体的回文串可以使用以下方法def longestPalindrome_construct(s: str) - str: from collections import Counter count Counter(s) left [] middle [] right [] for char, c in count.items(): if c % 2 0: left.extend([char] * (c // 2)) right.extend([char] * (c // 2)) else: left.extend([char] * (c // 2)) right.extend([char] * (c // 2)) middle.append(char) result .join(left) (middle[0] if middle else ) .join(reversed(right)) return result大小写敏感如果问题要求区分大小写处理方式与原问题相同只是字符集变大256 或更多。测试用例def test_longest_palindrome(): assert longestPalindrome(abccccdd) 7 assert longestPalindrome(a) 1 assert longestPalindrome(aa) 2 assert longestPalindrome(ab) 1 assert longestPalindrome(aba) 3 assert longestPalindrome(aabbcc) 6 assert longestPalindrome(aabbccd) 7 assert longestPalindrome() 0 assert longestPalindrome(AabB) 3 print(所有测试用例通过)实际应用场景最长回文串问题在现实中有很多应用。在文学创作中如果需要用给定的字符构造最长的回文诗句可以使用类似的算法。在密码学中某些算法需要构造对称结构。在游戏开发中如果需要生成镜像名称或对称的标识符。回文串的构造原理也是其他回文相关问题的基础如判断一个字符串是否能构成回文、添加最少的字符使字符串成为回文等。总结最长回文串问题虽然简单但蕴含了回文串构造的核心原理。哈希表用于统计字符频率然后基于统计结果计算最长回文串的长度。这个问题的关键洞察是偶数次的字符可以完整使用奇数次的字符只能使用其偶数部分多余的奇数部分可以放在回文串中间。这个问题也展示了如何将一个看似复杂的问题如构造回文串简化为一个简单的计数问题。希望通过本文的讲解读者能够深入理解回文串的构造原理并将其应用到更多类似问题的解决中。