LeetCode.409.Longest Palindrome 最长回文串

题目描述

409 Longest Palindrome
https://leetcode-cn.com/problems/longest-palindrome/

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example “Aa” is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

Input:
"abccccdd"

Output:
7

Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.

---

解题过程

用给定字符集中的字符拼凑回文串，这个问题可以转换为用给定字符集构造2个完全相等的串，然后反转一个拼一起就得到了回文串，中间还能夹一个单独的字符。
构造两个完全相等的串其实就是统计字符集中字符的出现次数，同一字符出现次数达到2次，就可以被放到回文串中，可以用一个 map 统计次数。
最后如果有剩下的单个的字符，可以夹到中间。

时间复杂度 O(n)，空间复杂度 O(n)

private static class SolutionV2020 {
    public int longestPalindrome(String s) {
        if (null == s || s.length() == 0) {
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();

        int length = 0;
        for (char c : chars) {
            Character character = Character.valueOf(c);
            int count = map.getOrDefault(character, 0) + 1;
            // 同一字符出现次数达到2次，就可以被放到回文串中
            if (count >= 2) {
                length += 2;
                count -= 2;
            }
            map.put(character, count);
        }
        // 中间可以放一个单独的字符
        for (int count : map.values()) {
            if (count > 0) {
                length++;
                break;
            }
        }
        return length;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_409_LongestPalindrome.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_409_LongestPalindrome.java

---