Easy

题目描述

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

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

示例 1:

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

示例 2:

输入:s = "a"
输出:1
解释:我们可以构造的最长的回文串是"a"，它的长度是 1。

提示:

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

解题思路

解题思路

这是一道贪心算法题目。要构造最长的回文串，我们需要理解回文串的特点：

  1. 回文串的结构特点：回文串从中心向两边对称，每个字符（除了可能的中心字符）都需要成对出现
  2. 字符配对策略：统计每个字符的出现次数，偶数次出现的字符可以全部使用，奇数次出现的字符可以使用 count - 1 个（保留成对的部分）
  3. 中心字符处理：如果存在出现奇数次的字符，我们可以选择其中一个放在回文串的中心位置

具体算法步骤：

  1. 使用哈希表统计每个字符的出现频次
  2. 遍历所有字符频次：
    • 如果频次为偶数，直接加入结果
    • 如果频次为奇数，加入 频次 - 1 到结果中
  3. 如果存在任何奇数频次的字符，结果加 1（作为中心字符）

这种贪心策略是最优的，因为我们尽可能使用了所有字符，只舍弃了多余的奇数字符。

代码实现

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char, int> count;
        for (char c : s) {
            count[c]++;
        }
        
        int result = 0;
        bool hasOdd = false;
        
        for (auto& p : count) {
            result += p.second / 2 * 2;  // 加上成对的字符
            if (p.second % 2 == 1) {
                hasOdd = true;  // 记录是否有奇数个字符
            }
        }
        
        return result + (hasOdd ? 1 : 0);  // 如果有奇数个字符，可以放一个在中间
    }
};

class Solution:
    def longestPalindrome(self, s: str) -> int:
        from collections import Counter
        
        count = Counter(s)
        result = 0
        has_odd = False
        
        for freq in count.values():
            result += freq // 2 * 2  # 加上成对的字符
            if freq % 2 == 1:
                has_odd = True  # 记录是否有奇数个字符
        
        return result + (1 if has_odd else 0)  # 如果有奇数个字符，可以放一个在中间

public class Solution {
    public int LongestPalindrome(string s) {
        Dictionary<char, int> count = new Dictionary<char, int>();
        
        foreach (char c in s) {
            if (count.ContainsKey(c)) {
                count[c]++;
            } else {
                count[c] = 1;
            }
        }
        
        int result = 0;
        bool hasOdd = false;
        
        foreach (var kvp in count) {
            result += kvp.Value / 2 * 2;  // 加上成对的字符
            if (kvp.Value % 2 == 1) {
                hasOdd = true;  // 记录是否有奇数个字符
            }
        }
        
        return result + (hasOdd ? 1 : 0);  // 如果有奇数个字符，可以放一个在中间
    }
}

var longestPalindrome = function(s) {
    const charCount = {};
    
    for (let char of s) {
        charCount[char] = (charCount[char] || 0) + 1;
    }
    
    let length = 0;
    let hasOdd = false;
    
    for (let count of Object.values(charCount)) {
        if (count % 2 === 0) {
            length += count;
        } else {
            length += count - 1;
            hasOdd = true;
        }
    }
    
    return hasOdd ? length + 1 : length;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，需要遍历字符串一次统计频次，然后遍历哈希表计算结果
空间复杂度O(1)，由于只包含英文字母，哈希表最多存储 52 个键值对，为常数空间

相关题目