Leetcode 409. Longest Palindrome

소문자 또는 대문자로 구성된 문자열이 주어지면

해당 문자로 작성할 수 있는 가장 긴 회문의 길이를 반환한다.

회문이란 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열을 뜻한다

문자는 대소문자를 구분하는데, 예를 들어,

"Aa"는 여기서 회문으로 간주되지 않는다.

---

접근 방법

처음엔 회문을 완성하는 것에 집중하고 문제를 접근했으나

회문의 length에 접근하는 것이 문제에서 요구하는 결과에

가까워지는 방법이란 것을 알았다.

 

문제를 해결 후 다시 생각을 해봤을 때

회문은 한 가지 방식으로 고정되어있는 것이 아니기에

애초에 회문을 만드는 방식으로 접근하는게 아녔다.

 

반복되는 문자를 처리하기 위해 예문을 확인해봤을 때

Input: s = "abccccdd"
Output: 7
Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.

a나 b는 짝이 없기 때문에 하나만 들어간 것을 확인할 수 있다.

여기서 유추해볼 수 있는 것은 반복되는 문자가 있다면

숫자를 증가시켜 length로 만들고, 단일 문자라면 그냥 패스하도록 두는 것이다.

문자가 하나만 있는 경우를 생각해 + 1만 해주는 방법도 필요했다.

 

중복 체크를 편하게 하기 위해 Map이나 Set을 사용해 접근하기로 했다.

Map에 문자 key가 있다면 숫자를 올리고,

그게 아니라면 Map에 문자를 넣어주기로 했다.

 

그런데 Map을 굳이 사용할 필요가 없었던 게

key에 해당 문자가 들어가고 value는 비어있게 된다.

Map을 사용해도 문제는 해결 가능하지만

뭔가 찜찜해서 Set을 사용해 문제를 해결하기로 했다.

 

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindrome = function(s) {
    
    const set = new Set();
    let result = 0;
    
       for(let i=0; i < s.length; i++) {
      if(set.has(s[i])) {
          result += 2;
          set.delete(s[i]);
      } else {
          set.add(s[i]);
      }
    }
    
    if(set.size > 0) result++;
    return result;
};