【C++】回文の順列を作るために削除すべき最小文字数を求めるアルゴリズム

問題の概要

文字列 S が与えられたとき、その文字列の順列（並べ替え）のうち少なくとも1つが回文になるようにするために、削除する必要のある文字数の最小値を求めます。

例

たとえば、str = "abcdba" の場合、'c' または 'd' のどちらか1文字を削除すれば、残りの文字で回文を作ることができます。

解法の考え方

この問題は、文字の出現頻度に着目することで効率的に解けます。ポイントは以下の通りです。

1. 回文には「偶数長」と「奇数長」の2種類があります。
2. 偶数長の回文では、すべての文字が偶数回出現しなければなりません。
3. 奇数長の回文では、1つの文字だけが奇数回出現し、それ以外のすべての文字は偶数回出現します。
4. したがって、各文字の出現回数を数え、奇数回出現している文字の総数をカウントします。答えは「奇数回出現する文字数 − 1」です（0の場合は0）。

つまり、奇数回出現する文字が n 個ある場合、そのうち n−1 個の文字を削除すれば、残りの文字で回文の順列が構成できるというわけです。

C++での実装例

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

int minCharactersRemoved(string str) {
    int hash[MAX] = {0};
    // 各文字の出現回数をカウント
    for (int i = 0; str[i]; ++i) {
        hash[str[i] - 'a']++;
    }
    int cnt = 0;
    // 奇数回出現する文字をカウント
    for (int i = 0; i < MAX; ++i) {
        if (hash[i] & 1) {
            ++cnt;
        }
    }
    return (cnt == 0) ? 0 : (cnt - 1);
}

int main() {
    string str = "abcdba";
    cout << "Minimum characters to be removed = " <<
    minCharactersRemoved(str) << endl;
    return 0;
}

実行結果

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

Minimum characters to be removed = 1

計算量について

このアルゴリズムの時間計算量は O(N)（N は文字列の長さ）、空間計算量は O(1)（英小文字26種類分の固定サイズ配列のみ使用）です。文字列を一度走査するだけで答えが求まるため、非常に効率的な解法といえます。