[greedy] 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.

소문자 또는 대문자로 구성된 문자열 s가 주어지면 해당 문자로 작성할 수 있는 가장 긴 팔레드롬의 길이를 반환합니다.

예를 들어, 여기서 "Aa"는 대소문자를 구분하지 않는다.

Palindrome : “aba”, “dccd”와 같이 reverse한 결과와 원본이 같은 단어를 말한다.

예시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

제약

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

첫번째 시도

const longestPalindrome = (s) => {
    const dict = {};
    let longestOddCnt = 0;
    let res = 0;
    
    
    [...s].forEach(c => {
        dict[c] ? dict[c]++ : dict[c] = 1;
    });
    
    Object.entries(dict).forEach(([c, cnt]) => {
        if (cnt % 2 === 1) {
            longestOddCnt = Math.max(longestOddCnt, cnt);
        } else {
            res += cnt;
        }
    });
    
    return res + longestOddCnt;
};

가장 긴 Palindrome을 구하는 케이스는 총 2개 라고 생각했다.

1. abba
2. abcba 혹은 abcccba

따라서 홀수개 최댓값 + 짝수개 합 으로 답을 구하도록 코드를 작성하였다.

글자를 사전형태로 담은 dict에 각 글자를 카운트하여 담아 둔다.

dict를 순회하며 value가 짝수일 때는 res 에 모두 더하고 홀수일 때는 홀수의 최대값만 구해서 더해주는 방식으로 진행했다.

하지만 아래와 같이 예외 케이스에 걸렸다.

https://leetcode.com/submissions/detail/597780846/testcase/

나의 로직의 문제점은 아래 부분이다.

dict를 순회하며 value가 짝수일 때는 res 에 모두 더하고 홀수일 때는 홀수의 최대값만 구해서 더해주는 방식으로 진행했다.

홀수일 때 최대값만 구해서 더해주었는데

홀수개여도 짝수개만 사용해서 더할수 있다는 것을 생각하지 못했다.

예를들어

const dict = {
  a: 5,
	b: 7,
	...
}

일 때, b의 7만 res 에 더해줬는데 a의 4를 더하고 b의 7을 더해주어야 했다.

최종 코드

const longestPalindrome = (s) => {
    const dict = {};
    let res = 0;
    
    
    [...s].forEach(c => {
        dict[c] ? dict[c]++ : dict[c] = 1;
    });
    
    Object.values(dict).forEach(cnt => {
        if (cnt % 2 === 1) {
            res += cnt - 1;
        } else {
            res += cnt;
        }
    });
    
    return Object.values(dict).find(v => v % 2 === 1) ? res + 1 : res;
};

• 입력받은 s 를 순회하며 각 글자에 대한 카운트 정보를 담은 dict 를 완성시킨다.
• dict 의 밸류를 순회하며 cnt 가 홀수 일 때는 cnt - 1, 즉 1을 빼서 짝수개 만큼 res 에 더해준다.
• cnt 가 짝수 일 때는 cnt를 그대로 더해준다.
• 최종적으로 모든 cnt를 축적한 res를 반환할 것인데 만약 순회하면서 cnt 가 홀수가 있다면 1을 더해서 출력하고 (가장 큰 홀수를 더해야 하므로), cnt에 홀수가 없다면 res 를 그대로 반환한다.