leetcode 409 Longest Palindrome 最长回文串(简单)

一、题目大意

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

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

示例 1:

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

示例 2:

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

提示:

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindrome
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、解题思路

思路：先统计每个字符出现的次数，再遍历统计后的字符次数，如果是偶数次，那么一定可以是回文字符串的一部分，加上该次数；如果是奇数n字，那么加上n-1次；最后判断如果出现过奇数次的字符，那么最后结果加1。

三、解题方法

3.1 Java实现

public class Solution {
    public int longestPalindrome(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        boolean odd = false;
        int ans = 0;
        for (Integer count : map.values()) {
            if (count % 2 == 0) {
                ans += count;
            } else {
                odd = true;
                ans += (count - 1);
            }
        }
        ans += odd ? 1 : 0;
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

四、总结小记

• 2022/8/31 不合理的管理是造成内耗的原因之一