(C++) - LeetCode (easy) 409. Longest Palindrome

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

Longest Palindrome - LeetCode

자료구조를 이용한 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

1. 홀수가 나온 문자 개수를 셀 변수 odds를 선언해 줍니다.

2. 문자별 빈도수를 저장할 map 변수 m을 선언해줍니다. s에 대해 for loop를 수행하며 값을 저장해줍니다.

📔 풀이과정

문자의 배치는 자유이므로 최대로 배치하기 위해서는 홀수인 부분만 짝수개를 사용하면 됩니다. 홀수가 나온 문자들을 한개씩 빼주고 마지막으로 홀수 문자를 가운데에 배치하면 정답을 구할 수 있습니다.

$$ { 최장 palindrome = s 길이 - 홀수가 나온 문자개수 + 홀수가 나온 문자 한개사용} $$

---

📕 Code

📔 C++

class Solution {
public:
    int longestPalindrome(string s) {
        int odds = 0;
        map <char, int> m;
        for(auto c : s) {
            m[c]++;
        }
        for(auto el : m) {
            if(el.second & 1) {
                odds++;
            }
        }
        return s.size() - odds + (odds > 0);
    }
};

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.