(Leet Code c++)Longest Palindrome

409. Longest Palindrome

 

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 here.

 

Example 1:

Input: s = "abccccdd" Output: 7 Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.

Example 2:

Input: s = "a" Output: 1

Example 3:

Input: s = "bb" Output: 2

 

Constraints:

• 1 <= s.length <= 2000
• s consists of lowercase and/or uppercase English letters only.

주어진 문자열 s로 가장 긴 팰린드롬을 만들어 그 길이를 리턴하면 된다.

 

대소문자가 같이 나오기 때문에 map을 통해 단어와 개수를 센다.

또한, 단어의 갯수가 홀수인 것은 odd 벡터에 갯수를 넣어주도록 한다.

 

우선 s를 순회해 map에 단어와 갯수를 저장한다.

 

이후 iterable을 이용해 map을 순회하도록 하자.

만약 itr->second가 홀수라면 odd 벡터에 넣어준다.

짝수라면 answer에 그대로 더해주자!

 

map 순회가 끝났다면 odd 벡터가 비어있는지 확인하자.

비어있다면 더 이상 더할 게 없다는 뜻이므로 바로 answer를 리턴.

 

비어있지 않다면, odd 벡터를 오름차순으로 정렬하여 순회하도록 하자.

odd 순회는 0 ~ odd.size() - 1 인덱스까지 순회한다.

그 이유는 odd의 가장 뒤에 있는 부분은 팰린드롬을 만들 수 있는 홀수 단어의 개수 중 가장 큰 값이기 때문에 무조건 answer에 더해야 한다.

이를 제외한 나머지 홀수 값은 -1을 하여 짝수로 만든 다음 answer에 더하면 된다.

 

 

class Solution {
public:
    int longestPalindrome(string s) {
        int answer = 0;
        vector<int> odd;
        map<char, int> m;
        
        cout << s.size() << endl;
        
        for(int i = 0; i < s.size(); i++){
            m[s[i]]++;
        }
        
        for(auto itr = m.begin(); itr != m.end(); itr++){
            if(itr->second % 2){
                odd.push_back(itr->second);
            } else{
                answer += itr->second;
            }
        }
        
        if(!odd.empty()){
            sort(odd.begin(), odd.end());
            
            for(int i = 0; i < odd.size() - 1; i++){
                answer += odd[i] - 1;
            }
            answer += odd.back();
        }
        
        return answer;
    }
};