LeetCode_贪心算法_简单_409.最长回文串

1.题目

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

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

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

示例 2：
输入：s = “a”
输入：1

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindrome

2.思路

（1）贪心算法
为了通过字符串 s 中的字符构造出的最长的回文串，我们可以考虑以下贪心策略：
① 如果 s 中的字符出现的次数均为偶数，那么由回文串的特点可知， s 中的全部字符可以用来构造最长回文串，并且其长度就为 s 的长度；
② 如果 s 中的字符出现的次数不全为偶数：
1）那么有一点可以确定的是，出现次数为偶数的字符可以全部用来构造最长回文串；
2）而对于出现次数为奇数的字符来说，为了构造最长回文串，我们可以将其中的任意一种字符放到回文串的最中间，其余的字符只取最大偶数个（即该字符出现的次数 - 1），然后平均分配到两边即可。

相关题目：
LeetCode_动态规划_中等_5.最长回文子串
LeetCode_回溯_动态规划_中等_131.分割回文串
LeetCode_双指针_简单_234.回文链表
LeetCode_动态规划_中等_516.最长回文子序列
LeetCode_字符串_中等_647. 回文子串
LeetCode_双指针_简单_1332.删除回文子序列

3.代码实现（Java）

//思路1————贪心算法
class Solution {
    public int longestPalindrome(String s) {
        // res 保存最终的结果，初始值为 0
        int res = 0;
        char[] chs = s.toCharArray();
        // haspMap 用来记录字符串 s 中出现的字符以及对应出现的次数
        Map<Character, Integer> hashMap = new HashMap<>();
        for (char c : chs) {
            hashMap.put(c, hashMap.getOrDefault(c, 0) + 1);
        }
        //遍历 hashMap 中所有的 value
        for (Integer cnt : hashMap.values()) {
            if (cnt % 2 == 0) {
                //当前字符出现的次数 cnt 为偶数，那么它一定是最长回文串的一部分
                res += cnt;
            } else {
                //当前字符出现的次数 cnt 为奇数，那么最长回文串一定包括 cnt - 1 个该字符
                res += cnt - 1;
            }
        }
        /*
            上面的 res 计算的是最长回文串长度为偶数的情况，下面再考虑其长度为奇数的情况：
            (1) 当其长度为奇数时，最中间的字符个数一定为奇数，例如 "dccaccd"、"ddaaadd"中的字符 a 分别出现了 1 次和 3 次；
            (2) 如果 s 中存在出现次数为奇数的字符时，任意选择其中的一种，将其放到最长回文串的中间即可，即 res 的值再加一；
            (3) 如果 s 中不存在出现次数为奇数的字符时，最长回文串的长度即为 s 的长度；
        */
        if (res < s.length()) {
            // res < s.length() 说明 s 中一定存在出现次数为奇数的字符
            res++;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34