【C++】文字を削除・並べ替えして作れる最長回文を求めるアルゴリズム

概要

与えられた文字列をもとに、文字を削除または並べ替え(シャッフル)することで形成できる最長の回文を求める問題です。最長の長さを持つ回文が複数存在する場合は、そのうちのどれか1つを返せばよいこととします。

入出力例

例1

入力: pqr
出力: p または q または r

例2

入力: ppqqrr
出力: pqrrqp または qprrpq または rqppqr など、長さ6の回文文字列

例3

入力: pqp
出力: pqp

解法のアプローチ

回文文字列は、次の3つの部分に分解して考えることができます。

• beg(前半): 文字列の先頭側の部分
• mid(中央): 中央の1文字(偶数長の場合は空)
• end(後半): 文字列の末尾側の部分

具体的には、奇数長 2n+1 の回文では、「beg」が最初の n 文字、「mid」が (n+1) 番目の1文字だけ、「end」が最後の n 文字で構成されます。一方、偶数長 2n の回文では、「mid」は常に空になります。また、回文である以上、「end」は必ず「beg」の逆順になるという性質があります。

この観察を解法に活かします。文字の並べ替えが許されているため、入力文字列内での文字の順序は一切問題になりません。そこで、まず各文字の出現頻度を数えます。その上で、以下のように構成します。

• 偶数回(2n回)出現する文字: n 文字を「beg」に、残り n 文字を「end」に配置すればよいので、すべて出力文字列に使用できます。
• 奇数回(2n+1回)出現する文字: いずれか1文字を「mid」に配置し、残りの 2n 文字は半分ずつに分けて「beg」と「end」に追加します。

C++実装例

// 与えられた文字列から文字を削除または並べ替えて
// 作られる最長回文を求めるC++プログラム
#include <bits/stdc++.h>
using namespace std;

// 文字列から文字を削除または並べ替えることで
// 作られる最長回文を返す関数
string findLongestPalindrome(string str1){
    // 各文字の出現頻度を格納する配列
    int count1[256] = { 0 };
    // 入力文字列中の各文字の出現頻度を数える
    for (int i = 0; i < str1.size(); i++)
        count1[str1[i]]++;
    // 回文文字列は3つの部分で構成される
    // beg1 + mid1 + end1
    string beg1 = "", mid1 = "", end1 = "";
    // ここでは簡単のため小文字のみを扱う。
    // 任意の文字集合に対応するよう拡張することも容易
    for (char ch1 = 'a'; ch1 <= 'z'; ch1++){
        // 現在の文字の出現頻度が奇数の場合
        if (count1[ch1] & 1){
            // mid1に入るのは1文字だけ。次に奇数頻度の
            // 文字が見つかった場合は上書きされる
            mid1 = ch1;
            // 頻度を偶数に整えて、同じ文字を
            // もう一度処理するためにデクリメント
            count1[ch1--]--;
        }
        // 現在の文字の出現頻度が偶数の場合
        else{
            // カウントが n(偶数)なら、n/2 文字を beg に
            // 追加し、残りの n/2 文字は end の一部になる
            for (int i = 0; i < count1[ch1]/2 ; i++)
                beg1.push_back(ch1);
        }
    }
    // end は beg の逆順
    end1 = beg1;
    reverse(end1.begin(), end1.end());
    // 回文文字列を返す
    return beg1 + mid1 + end1;
}

// 動作確認用コード
int main(){
    string str1 = "pqqprrs";
    cout << findLongestPalindrome(str1);
    return 0;
}

実行結果

pqrsrqp