99클럽 코테 스터디 38일차 TIL Longest Palindrome

# 오늘의 학습 키워드 

탐욕법(Greedy)

 

# 오늘의 문제 

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

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.

 

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

Explanation: The longest palindrome that can be built is "a", whose length is 1.

 

Constraints:

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

 

# 나의 풀이방식 

class Solution {
    public int longestPalindrome(String s) {
        int[] cnt = new int[128]; // 각 문자의 카운트를 저장하는 배열(ASCII size)

        // 문자열에서 문자 수
        for (char c : s.toCharArray()) {
            cnt[c]++;
        }

        int res = 0;
        boolean hasOdd = false;

        // 'A'부터 'z'까지 가능한 모든 문자 반복
        for (int i = 'A'; i <= 'z'; i++) {
            boolean odd = cnt[i] % 2 == 1;
            if (odd) hasOdd = true;
            res += cnt[i] - (odd ? 1 : 0); // 카운트가 홀수인 경우 -1
        }

        // 홀수인 문자가 하나 이상 있으면 +1
        return res + (hasOdd ? 1 : 0);
    }
}