Leet Code - 409. Longest Palindrome(C++)

예제: Longest Palindrome

문제
Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example "Aa" is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

Input:
"abccccdd"

Output:
7

Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

풀이

주어진 알파벳으로 만들 수 있는 palindrome 문자 중 최대 길이를 반환하는 문제이다.

주어진 알파벳들의 짝수 개수의 모든 합 + 최대 홀수의 개수 + (홀수의 개수 - 1)을 구하여 더하면 된다.

전체적인 소스코드는 아래와 같다.

소스 코드

class Solution {
public:
	int longestPalindrome(string s) {
		int alphabet[52] = { 0 };
		for (char ch : s) {
			if (ch >= 'A' && ch <= 'Z') {
				alphabet[ch - 'A' + 26]++;
			}
			else {
				alphabet[ch - 'a']++;
			}
		}

		int res = 0, odd = 0;
		for (int i = 0; i < 52; i++) {
			if (alphabet[i] % 2 == 0)
				res += alphabet[i];
			else {
				if (odd == 0) {
					odd = alphabet[i];
				}
				else if (odd < alphabet[i]) {
					res += (odd - 1);
					odd = alphabet[i];
				}
				else {
					res += (alphabet[i] - 1);
				}
			}
		}

		return res + odd;
	}
};

풀이 후기

(홀수의 개수 - 1)를 빠뜨려서 헤맸던 문제이다. 문제의 이해가 중요한 문제였다.