[JAVA | LeetCode] 409. Longest Palindrome

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

문제

소문자 또는 대문자로 구성된 문자열 s가 있다.
해당 문자로 만들 수 있는 가장 긴 회문의 길이를 반환한다.

입력 예

Example 1
Input: s = "abccccdd"
Output: 7
-> 만들 수 있는 가장 긴 회문은 dccaccd로, 길이는 7이다.

Example 2
Input: s = "a"
Output: 1
-> 만들 수 있는 가장 긴 회문은 a로, 길이는 1이다.

제한사항

• 1 <= s.length <= 2000
• s는 영문 대소문자로만 구성된다.

풀이

1. 문자열 내의 문자들을 HashMap에 담고 value로 카운트한다.
2. 문자의 개수가 짝수일 경우: 양쪽으로 나누어 붙일 수 있다. (ex- a의 개수가 4이면, aa__aa 처럼 회문이 되도록 한다.) 따라서 개수 그대로 answer에 더해준다.
3. 문자의 개수가 홀수일 경우: boolean 플래그를 두고, 플래그가 false일 경우 answer에 개수를 더해준 후 플래그를 true로 바꿔준다. (ex- b의 개수가 5이면, bbbbb처럼 중간을 기준으로 회문이 되도록 한다.)
4. 이후에 문자 개수가 홀수가 나온다면, 개수에서 -1해준 값을 answer에 더해준다. 최대한 긴 회문이 나오기 위해!

class Solution {
    public int longestPalindrome(String s) {
        int answer = 0;
        HashMap<String, Integer> hm = new HashMap<>();
        boolean odd = false;
        for (String str : s.split("")) {
            hm.put(str, hm.getOrDefault(str, 0) + 1);
        }

        for (String str : hm.keySet()) {
            if (hm.get(str) % 2 == 0) {
                answer += hm.get(str);
            } else {
                if (odd == true) {
                    if(hm.get(str) > 1) answer += hm.get(str) - 1;
                } else {
                    answer += hm.get(str);
                    odd = true;
                }
            }
        }
        return answer;
    }
}

결과