Longest Palindrome

https://leetcode.com/problems/longest-palindrome/description/

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.

Thoughts

形成回文只要左右对称即可。因此对于偶数个数的字符只要分别往两边扔即可，因此可以全部用到；对于奇数个的字符，把它减一个可以全部按照偶数同理往两边扔。我们可以从所有奇数次的字符中选择一个字符放中间。

Code

class Solution {
    public int longestPalindrome(String s) {
        Map<Character, Integer> freq = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            freq.put(s.charAt(i), freq.getOrDefault(s.charAt(i), 0) + 1);
        }
        int res = 0;
        boolean single = false;
        for (Character c : freq.keySet()) {
            if (freq.get(c) % 2 == 0) {
                res += freq.get(c);
            } else {
                single = true;
                res += freq.get(c) - 1;
            }
        }

        if (single) {
            res++;
        }

        return res;
    }
}

Analysis

时间复杂度O(n), 空间O(n).

Ver.2

我们想知道每个字符频率是偶数次还是奇数次，我们可以用一个set, 当set里有该数字时，表示之前是奇数次.在set把当前字符删除表示现在是偶数次。当遇到的字符之前出现的次数已经是奇数次时，我们就可以直接让结果+2. 否则我们可以放入set中，等是否未来能凑成偶数。

https://leetcode.com/problems/longest-palindrome/discuss/