JavaScript로 만들 수 있는 가장 긴 회문(Palindrome) 문자열의 길이 찾기

소문자 또는 대문자로만 구성된 문자열 s가 주어졌을 때, 이 문자열에 포함된 글자들을 조합하여 만들 수 있는 가장 긴 회문(palindrome)의 길이를 반환하는 문제입니다. 단, 대소문자는 서로 구분해야 하므로 예를 들어 "Aa"는 회문으로 간주하지 않습니다.

문제 예시

입력 문자열이 다음과 같다고 해봅시다.

const str = "abccccdd";

이 경우 출력값은 7이어야 합니다. 그 이유는 주어진 글자들로 만들 수 있는 가장 긴 회문이 "dccaccd"이며, 그 길이가 정확히 7이기 때문입니다.

접근 방법

회문은 좌우가 대칭을 이루는 문자열입니다. 따라서 각 문자는 짝수 개씩 있어야 양쪽에 배치할 수 있고, 만약 홀수 개인 문자가 하나라도 존재한다면 그중 한 개를 가운데에 놓아 회문 길이를 1 늘릴 수 있습니다.

이 원리를 활용하면 Set 자료구조를 이용해 간단하게 해결할 수 있습니다.

현재 문자가 Set에 없다면 추가합니다. (짝이 아직 없음)
이미 Set에 있다면 짝이 완성된 것이므로 카운트를 2 증가시키고 Set에서 제거합니다.
모든 문자를 순회한 뒤 Set에 남은 문자가 있다면, 그중 하나를 회문의 중앙에 배치할 수 있으므로 결과에 1을 더합니다.

구현 코드

const str = "abccccdd";
const longestPalindrome = (str) => {
    const set = new Set();
    let count = 0;
    for (const char of str) {
        if (set.has(char)) {
            count += 2; set.delete(char);
        }
        else {
            set.add(char);
        }
    }
    return count + (set.size > 0 ? 1 : 0);
};
console.log(longestPalindrome(str));

코드 동작 원리

빈 Set과 펜딩 카운트 변수를 초기화합니다.
문자열을 한 글자씩 순회하면서 해당 문자가 Set에 존재하는지 확인합니다.
존재한다면 앞서 같은 문자가 한 번 나왔다는 의미이므로 한 쌍이 완성됩니다. 카운트를 2 증가시키고 Set에서 제거합니다.
존재하지 않는다면 아직 짝을 찾지 못한 상태이므로 Set에 추가해 둡니다.
순회가 끝난 후 Set에 문자가 남아 있다면, 홀수 개로 등장한 문자가 있다는 뜻입니다. 이 중 한 글자를 회문의 정중앙에 배치할 수 있으므로 최종 결과에 1을 더해 반환합니다.

이 알고리즘의 시간 복잡도는 문자열을 한 번만 순회하므로 O(n)이며, Set에는 알파벳 종류만큼(영문 기준 최대 52개)만 저장되므로 공간 복잡도는 사실상 O(1)입니다.

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다.