江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode第409题：最长回文串

给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。 在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

难度：简单

题目链接：LeetCode第409题

题目描述

给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。

在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

示例 1：

输入: s = "abccccdd"
输出: 7
解释: 我们可以构造的最长的回文串是"dccaccd", 它的长度是7。

示例 2：

输入: s = "a"
输出: 1

示例 3：

输入: s = "bb"
输出: 2

提示：

  • 1 <= s.length <= 2000
  • s 只由小写和/或大写英文字母组成

解题思路

这道题目的核心思路是：

  1. 统计每个字符出现的次数
  2. 偶数次的字符可以全部用于构建回文串
  3. 奇数次的字符可以使用偶数个（最多减去1个）
  4. 如果有任何奇数次的字符，可以在中间放一个字符

算法流程

  1. 使用哈希表或数组统计每个字符出现的次数
  2. 遍历字符频次：
    • 对于偶数次出现的字符，全部计入结果
    • 对于奇数次出现的字符，计入其偶数部分（次数-1）
  3. 如果存在奇数次字符，最终结果加1（可以放在中间）

代码实现

C# 实现

public class Solution {
    public int LongestPalindrome(string s) {
        int[] count = new int[128];  // ASCII字符集
        
        // 统计字符频次
        foreach (char c in s) {
            count[c]++;
        }
        
        int length = 0;
        bool hasOdd = false;
        
        // 计算可以使用的字符数
        foreach (int freq in count) {
            length += freq / 2 * 2;  // 取偶数部分
            if (freq % 2 == 1) {     // 记录是否有奇数次字符
                hasOdd = true;
            }
        }
        
        // 如果有奇数次字符，可以放一个在中间
        return length + (hasOdd ? 1 : 0);
    }
}

Python 实现

class Solution:
    def longestPalindrome(self, s: str) -> int:
        # 使用Counter统计字符频次
        from collections import Counter
        count = Counter(s)
        
        length = 0
        has_odd = False
        
        # 计算可以使用的字符数
        for freq in count.values():
            length += freq // 2 * 2  # 取偶数部分
            if freq % 2 == 1:        # 记录是否有奇数次字符
                has_odd = True
        
        # 如果有奇数次字符，可以放一个在中间
        return length + (1 if has_odd else 0)

C++ 实现

class Solution {
public:
    int longestPalindrome(string s) {
        vector<int> count(128, 0);  // ASCII字符集
        
        // 统计字符频次
        for (char c : s) {
            count[c]++;
        }
        
        int length = 0;
        bool hasOdd = false;
        
        // 计算可以使用的字符数
        for (int freq : count) {
            length += freq / 2 * 2;  // 取偶数部分
            if (freq % 2 == 1) {     // 记录是否有奇数次字符
                hasOdd = true;
            }
        }
        
        // 如果有奇数次字符，可以放一个在中间
        return length + (hasOdd ? 1 : 0);
    }
};

执行结果

C# 实现

  • 执行用时：68 ms
  • 内存消耗：35.9 MB

Python 实现

  • 执行用时：36 ms
  • 内存消耗：15.2 MB

C++ 实现

  • 执行用时：0 ms
  • 内存消耗：6.5 MB

性能对比

语言 执行用时 内存消耗 特点
C# 68 ms 35.9 MB 代码结构清晰，性能一般
Python 36 ms 15.2 MB 使用Counter类，代码简洁
C++ 0 ms 6.5 MB 性能最优，内存占用最小

代码亮点

  1. 🎯 使用数组/哈希表高效统计字符频次
  2. 💡 巧妙处理奇偶数字符的计数
  3. 🔍 优化空间复杂度，使用固定大小数组
  4. 🎨 代码结构简洁，逻辑清晰

常见错误分析

  1. 🚫 忽略大小写区分
  2. 🚫 错误处理奇数次字符
  3. 🚫 未考虑可以放一个字符在中间
  4. 🚫 统计数组大小选择不当

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
哈希表统计 O(n) O(1) 实现简单，直观 需要额外空间
位运算 O(n) O(1) 空间效率高 实现复杂，不直观

相关题目

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第409题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！