C++で回文に並べ替え可能な最大の偶数長部分文字列を求める方法

問題の概要

文字列が与えられたとき、その中から「並べ替えると回文になる」部分文字列を探し、その最大の長さを求めるのがこの問題です。ただし、今回扱うのは偶数長の部分文字列に限られます。

具体例

入力文字列が「5432112356」の場合、答えは 6 になります。「321123」という部分文字列は並べ替えると「123321」という回文になり、その長さがちょうど 6 であるためです。

アルゴリズムの考え方

ある部分文字列が回文に並べ替えられるかどうかは、各文字の出現回数だけで判定できます。ポイントは次のとおりです。

• 奇数長の部分文字列は候補から除外する: 今回は偶数長のみを対象とするため、長さが奇数の部分文字列は最初に排除します。
• 偶数長の場合は「全文字が偶数回出現」が条件: 偶数長の部分文字列が回文に並べ替えられるのは、含まれるすべての文字が偶数回出現しているときだけです。この判定には unordered_map による文字数カウントを利用します。
• 再帰的に範囲を広げて探索する: 条件を満たす部分文字列が見つかったら解の候補として記録し、end を1つ進めて次の文字を追加した場合についても同様に判定します。最終的に、得られたすべての候補の中で最大の長さを返します。

なお、この実装は考えられる範囲を網羅的に調べる方式のため、計算量は文字列長に対して急激に増大します。学習用途や短い入力には十分有効ですが、より長い文字列を扱う場合は「各文字の出現回数の偶奇をビット列で管理し、先頭からの累積 XOR を記録する」などの効率的な手法を検討するとよいでしょう。

C++による実装例

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

unordered_map<int, int> countt;

// 登場するすべての文字が偶数回出現していれば true を返す
bool isPalindromePossible(unordered_map<int, int>& cnt) {
    for (auto key : cnt) {
        if (key.second % 2 != 0) {
            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() {
    string str = "5432112356";
    int start = 0, end = 0;
    cout << "Maximum palindrome length = "
         << getMaxPalindrome(str, countt, start, end) << endl;
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次のような出力が得られます。

Maximum palindrome length = 6

コードのポイント

• isPalindromePossible() は、マップ内のすべての文字について出現回数が偶数かどうかを確認し、1つでも奇数があれば false を返します。
• getMaxPalindrome() は現在の区間 [start, end] を基準に、「end を伸ばす」場合と「start を進める」場合の両方を再帰的に試して、最大の長さを求めます。
• 長さが偶数のときだけ回文判定を行うことで、無駄な計算を抑えています。