[LeetCode] 409. Longest Palindrome

https://leetcode.com/problems/longest-palindrome/description/?source=submission-noac

leetcode - Longest Palindrome

문제 유형 : 문자열 처리

문제 난이도 : Easy

 

문제

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

Letters are case sensitive, for example, "Aa" is not considered a palindrome.

 

문자열 s가 주어집니다. 이들로 만들 수 있는 가장 긴 팰린드롬(회문)을 만드시오. 글자는 대소문자를 구분합니다.

 

풀이

팰린드롬은 양쪽이 대칭이어야 한다.

각 문자의 개수를 세준다.

 

홀수면 1을 뺴서 누적시키고, 짝수면 그냥 누적시킨다. 대칭되어야 하기 때문에, 홀수는 하나 잘라야 한다.

그러나, 가운데에 홀수를 하나 넣을 수 있으므로, 홀수가 하나라도 있다면 1을 또 더해주면 된다.

 

코드

C++

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char, int> mp;

        for(char ch : s) {
            mp[ch]++;
        }

        int ans = 0;
        bool odd = false;
        for(auto &element : mp) {
            if(!(element.second%2)) ans += element.second;
            else {
                odd = true;
                ans += element.second-1;
            }
            
        }

        return odd? ans+1: ans;
    }
};