【算法|贪心算法系列No.5】leetcode409. 最长回文串

个人主页：兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【LeetCode】
🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助
🍓希望我们一起努力、成长，共同进步。

1️⃣题目描述

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

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

示例1：

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

示例2：

输入:s = “a”
输出:1

示例3：

输入:s = “aaaaaccc”
输出:7

注意：

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

2️⃣题目解析

通过数组模拟哈希表将字符串中每个字符出现的次数记录下来，然后计算回文串中能够成对的字符个数。每个字符能够成对的个数就是其出现次数除以 2 的结果再乘以 2。最后，判断所有能够成对的字符数是否小于原字符串长度，如果小于，则说明可以选取一个单独的字符作为回文串的中心，使得最终回文串长度加 1。

3️⃣解题代码

class Solution {
public:
    int longestPalindrome(string s) {
        int hash[127] = { 0 };
        for(char x : s) hash[x]++;
        
        int ret = 0;
        for(int x : hash) ret += x / 2 * 2;
        return ret = ret < s.size() ? ret + 1 : ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11

最后就通过啦！！！