문제
풀이
아이디어
팰린드롬은 앞뒤가 대칭인 문자열이니까 팰린드롬을 구성하는 문자의 등장 횟수에는 규칙이 있다.
- 짝수 번 등장한 문자: 전부 팰린드롬 양쪽에 대칭으로 배치할 수 있으므로 전부 사용 가능하다.
- 홀수 번 등장한 문자: 짝수 부분(전체 - 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 (상수)
end