C++로 찾는 회문 순열이 가능한 최대 짝수 길이 부분 문자열

문제 개요

하나의 문자열이 주어졌을 때, 그 안의 부분 문자열 중에서 문자들을 재배열해 회문(Palindrome)을 만들 수 있는 것의 최대 길이를 구하는 것이 이 문제의 목표입니다.

예시

입력 문자열이 "5432112356"이라면 정답은 6입니다. 가장 긴 회문 부분 문자열이 "321123"이며, 이는 재배열하면 "123321"이라는 회문이 되고 그 길이가 6이기 때문입니다.

알고리즘

회문은 좌우가 대칭되는 구조이므로, 짝수 길이의 회문이 되려면 포함된 모든 문자가 반드시 짝수 번씩 등장해야 합니다. 이 성질을 활용하면 다음과 같이 문제를 풀 수 있습니다.

• 부분 문자열의 길이가 홀수라면 최종 해답 후보에서 제외합니다.
• 부분 문자열의 길이가 짝수라면, 해시 맵(unordered_map)으로 문자별 등장 횟수를 세어 모든 문자가 짝수 번 등장하는지 확인합니다. 조건을 만족하면 가능한 해답으로 채택합니다.
• 끝 인덱스(end)를 하나 늘려 다음 부분 문자열을 만들고, 더 길면서 조건을 만족하는 부분 문자열이 존재하는지 재귀적으로 검사한 뒤, 모든 가능한 해답 중 최댓값을 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

unordered_map<int, int> countt;

// 모든 문자가 짝수 번 등장하는지 확인
bool isPalindromePossible(unordered_map<int, int> &countt) {
    for (auto key : countt) {
        if (key.second & 1) {
            return false;
        }
    }
    return true;
}

int getMaxPalindrome(string str, unordered_map<int, int> &countt, int start, int end) {
    if (end == str.length()) {
        if ((end - start) % 2 == 0)
            if (isPalindromePossible(countt))
                return end - start;
        return 0;
    } else {
        if ((end - start) % 2 == 0) {
            if (isPalindromePossible(countt)) {
                countt[str[end]]++;
                return max(end - start, getMaxPalindrome(str, countt, start, end + 1));
            } else {
                countt[str[end]]++;
                return getMaxPalindrome(str, countt, start, end + 1);
            }
        } else {
            countt[str[end]]++;
            unordered_map<int, int> c(countt.begin(), countt.end());
            int length = getMaxPalindrome(str, c, start, end + 1);
            countt[str[end]]--;
            countt[str[start]]--;
            return max(length, getMaxPalindrome(str, countt, start + 1, end));
        }
    }
}

int main(int argc, char const *argv[]) {
    string str = "5432112356";
    int start = 0, end = 0;
    cout << "Maximum palindrome length = " << getMaxPalindrome(str, countt, start, end) << endl;
    return 0;
}

코드 설명

• isPalindromePossible() – 해시 맵에 저장된 각 문자의 등장 횟수를 검사하여, 하나라도 홀수 번 등장하면 false, 모두 짝수 번이면 true를 반환합니다.
• getMaxPalindrome() – 시작 인덱스(start)와 끝 인덱스(end)를 조절해 가며 모든 부분 문자열을 재귀적으로 탐색하고, 길이가 짝수이면서 회문 재배열이 가능한 경우 그중 가장 긴 길이를 반환합니다.
• main() – 예제 문자열 "5432112356"에 대해 위 함수를 호출하고 결과를 출력합니다.

실행 결과

위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.

Maximum palindrome length = 6

복잡도 분석

모든 시작·끝 조합을 재귀적으로 살펴보고 매 단계마다 해시 맵을 복사·검사하므로, 문자열의 길이를 N이라 할 때 시간 복잡도는 대략 O(N³)입니다. 각 문자 등장 횟수의 홀짝성을 비트마스크로 관리하고 접두사 상태(prefix state)를 활용하면 O(N)까지 최적화할 수 있습니다.