LeetCode #409 Longest Palindrome

問題概要

入力値：s
出力値：num
return the length of the longest palindrome that cane be build with those letters.
問題のリンク

入力例

nums: "aabbc"
answer: 5 ("abcba")

解答例1

計算量：O(n)
Using dict that contains count of each char
if all counts are even numbers→return sum of the numbers
if even count exists then the count has to be minus 1
Python

from collections import defaultdict

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        num_dict = defaultdict(int)
        for char in s:
            num_dict[char] += 1
        result = 0
        odd_exist = False
        for count in num_dict.values():
            if count % 2 == 0:
                result += count
            else:
                odd_exist = True
                result += count - 1
        if odd_exist:
            result += 1
        return result

Runtime: 7ms
Beats: 98.97%

C++

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char, int> num_dict;
        for (char val : s) {
            if (num_dict.contains(val)) {
                num_dict[val] += 1;
            } else {
                num_dict[val] = 1;
            }
        }
        int result = 0;
        bool odd_exist = false;
        for (auto pair : num_dict) {
            if (pair.second % 2 == 0) {
                result += pair.second;
            } else {
                odd_exist = true;
                result += pair.second - 1;
            }
        }
        if (odd_exist) {
            result += 1;
        }
        return result;
    }
};

Runtime: 0ms
Beats: 100%