[LeetCode] 409.Longest Palindrome

LeetCode #409

문제

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.

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.
"abccccdd" => "dccadcc" ==> 7
여기서 구해야하는건 dccadcc 라는 결과가 아닌 7이라는 String 의 길이이다.

2.
"a" "b" "cccc" "dd" 
각 알파벳 별로 분리해서 생각한다.
각 각의 알파벳 별로 
   2-1. length 가 짝수인 경우 Palindrome(회문)이 가능하다
   2-2. length 가 홀수인 경우,
      2-2-1. 회문이 안 되지만, 문자열의 중앙에서 회문이 가능하다.
      2-2-2. 가장 큰 홀수를 제외한 나머지는 -1 하여 짝수가 되면 회문이 가능하다.

3.
알파벳이 정렬되어 있지 않으니 각 알파벳 별 length counting을 위해 map을 사용한다.
홀수인 경우, 홀수 중 가장 큰 수를 제외하고 나머지는 짝수로 만들기 위해 -1을 해주는 과정을 간단하게 하기 위해 
홀수인 수들의 합에 홀수인 수들의 개수를 빼주고, + 1을 해준다.
여기서 발생한 버그로 홀수인 수가 없는 경우 +1 만 남아서 잘못된 결과를 반환하게 된다.
이런 상황이 발생하지 않도록 예외로 홀수의 합이 0 인 경우는 0이 되도록 한다.