409. Longest Palindrome

리트코드 409번 풀이

문제

Longest Palindrome

풀이

아이디어

팰린드롬은 앞뒤가 대칭인 문자열이니까 팰린드롬을 구성하는 문자의 등장 횟수에는 규칙이 있다.

• 짝수 번 등장한 문자: 전부 팰린드롬 양쪽에 대칭으로 배치할 수 있으므로 전부 사용 가능하다.
• 홀수 번 등장한 문자: 짝수 부분(전체 - 1)은 양쪽에 배치하고, 남은 1개는 팰린드롬 가운데에 하나만 놓을 수 있다.

따라서 문자열을 한 번 순회해서 각 문자의 등장 횟수를 Map에 저장한 뒤, 홀수 번 등장한 문자가 하나라도 있으면 가운데에 1개를 추가해주면 된다.

코드

function longestPalindrome(s: string): number {
  const map = new Map();

  for (const c of s) map.set(c, (map.get(c) ?? 0) + 1);

  let maxLength = 0;
  let isOddExist = false;
  map.forEach((value) => {
    if (value % 2 === 0) {
      maxLength += value;
    } else {
      maxLength += value - 1;
      isOddExist = true;
    }
  });

  return maxLength + (isOddExist ? 1 : 0);
}

시간 / 공간 복잡도

• 시간 복잡도: O(n)
• 공간 복잡도: O(1) — 알파벳 대소문자만 등장하므로 Map 크기는 최대 52 (상수)