가장 긴 회문(Palindrome) 문자열 구하기 (그리디)

김민아·2023년 2월 8일
0

409. Longest Palindrome

409. Longest Palindrome

문제

앞으로 읽으나 뒤로 읽으나 동일한 문자열을 펠린드롬(palindrome), 회문이라고 한다.

주어진 s문자열을 이용하여 가장 긴 회문을 반환하는 문제이다.

테스트 케이스

Input: s = "abccccdd"
Output: 7

풀이

주어진 s 중 각 문자열이 등장하는 횟수를 해시 테이블에 저장한다. 그 중 갯수의 문자열은 제외한다. 그 중 중앙을 차지하는 문자열 하나를 제외하고 s.length를 반환한다.

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindrome = function(s) {
  const charCounts = new Map()
  let oddCount = 0;

  for (let char of s) {
    charCounts.set(char, (charCounts.get(char) || 0) + 1);
  }

  for (let count of charCounts.values()) {
    // 홀수 문자열 갯수 찾기 
    if (count % 2 !== 0) {
      // 1, 1 -> 2
      oddCount++
    }
  }
  // s의 길이에서 홀수 문자열은 하나만 남겨두고 전부 제외 
  // 즉, 중앙에 들어갈 하나만 남겨둘 수 있음.
  return s.length - Math.max(0, oddCount - 1)
};

0개의 댓글