409. Longest Palindrome

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

Longest Palindrome - LeetCode

 

문제

가장 긴 펠린드롬 문자를 만들어라.

 

이문제는 문자열에서 가장 긴 펠린드롬을 찾는 문제가 아니라 주어진 문자열을 조합하여 가장 긴 펠린드롬을 찾는 문제이다. 첫 번째로 생각할 수 있는 게 문자열이 길이가 짝수라면 펠린드롬이 길이는 최대 2*N의 길이를 가질 것이다. 

두 번째로 생각 되는 건 만약 주어진 문자열이 길이가 홀수라면 최대 2*N + 1에 길이를 갖는 펠린드롬을 만들 수 있다. 이 두 가지를 생각하고 코드를 작성하였다.

 

코드

문자열을 모두 map에 삽입하고 value를 증가한다.

반복문으로 map을 순회하면서 value 값이 홀수 여부를 확인한다.

class Solution {
public:
    int longestPalindrome(string s) {

        map<char, int> m;
        
        for(auto c:s) {
            m[c]++;
        }
        
        int hasOdd = 0;
        int sol = 0;
        for(auto a:m) {
            sol += a.second / 2;
            if(a.second & 1) {
                hasOdd = true;
            }
        }
        
        sol = sol * 2 + hasOdd;
        return sol;
    }
};