C++で文字を並べ替えて回文を形成する方法

任意の長さの文字列「str」が与えられたとき、入力文字列から文字を追加・削除することなく、出力が回文（パリンドローム）となるように文字を並べ替えることが課題です。回文とは、前から読んでも後ろから読んでも同じ発音・同じ並びになる文字列のことを指します。

入出力シナリオの例

入力 − string str = "itnin"

出力 − 回文を形成できる場合の文字の並べ替え結果：nitin

説明 − 文字列型変数 str が与えられています。入力文字列の文字を回文となるように並べ替え、不可能な場合は「NOT POSSIBLE」を返します。この入力文字列の場合、出力は「nitin」となります。

入力 − string str = "baaaba"

出力 − 回文を形成できる場合の文字の並べ替え結果：aabbaa

説明 − 同様に、文字列型変数 str の文字を回文となるように並べ替えます。この入力文字列の場合、出力は「aabbaa」となります。

プログラムで使用するアプローチ

• 文字列型変数 str を入力として受け取り、文字列のサイズを計算して length という変数に格納します。

• データを関数 Rearrangement(str, length) に渡します。

• 関数 Rearrangement(arr, length) の内部では以下の処理を行います。

  • char 型と int 型のペアを格納する unordered_map 型の変数「um」を作成します。

  • int 型変数 total を宣言し、0 で初期化します。

  • char 型変数「ch」と、string 型変数 str_1 および str_2 を作成します。

  • i を 0 から length 未満まで FOR ループで繰り返します。ループ内で um[str[i]] を 1 ずつインクリメントし、各文字の出現回数をカウントします。

  • マップ「um」を反復処理する FOR ループを開始します。ループ内で、it.second % 2 が 0 でない場合（奇数回出現する文字がある場合）は total を 1 増加させ、ch に it.first を設定します。

  • total が 1 より大きい場合、または total が 1 かつ length % 2 == 0 の場合は 0 を返します（回文が成立しないため）。

  • マップ「um」を再度反復処理する FOR ループを開始します。ループ内で string(it.second / 2, it.first) を作成し、str_1 = str_1 + str、str_2 = str + str_2 として前半部分と後半部分を構築します。

  • total == 1 の場合は str_1 + ch + str_2 を返し、それ以外の場合は str_1 + str_2 を返します。

• 結果を出力します。

コード例

#include <bits/stdc++.h>
using namespace std;
string Rearrangement(string str, int length){
    unordered_map<char, int> um;
    int total = 0;
    char ch;
    string str_1 = "";
    string str_2 = "";

    for (int i = 0; i < length; i++){
        um[str[i]]++;
    }
    for(auto it : um){
        if(it.second % 2 != 0){
            total++;
            ch = it.first;
        }
    }
    if(total > 1 || total == 1 && length % 2 == 0){
        return 0;
    }
    for(auto it : um){
        string str(it.second / 2, it.first);
        str_1 = str_1 + str;
        str_2 = str + str_2;
    }
    if(total == 1){
        return str_1 + ch + str_2;
    }
    else{
        return str_1 + str_2;
    }
}
int main(){
    string str = "itnin";
    int length = str.size();
    cout<<"Rearrangement of characters to form palindrome if possible is: "<<Rearrangement(str, length);
    return 0;
}

出力

上記のコードを実行すると、以下の出力が生成されます。

Rearrangement of characters to form palindrome if possible is: nitin

まとめ

このアルゴリズムのポイントは、各文字の出現回数を unordered_map でカウントし、奇数回出現する文字が高々1種類であるかどうかを確認することです。奇数回出現する文字が2種類以上ある場合、その文字列はどのように並べ替えても回文にできません。逆に条件を満たす場合は、各文字の半分を前半に配置し、残りの半分を逆順で後半に配置することで回文を構築できます。文字列の長さが奇数の場合は、中央に奇数回出現した文字を1つ配置します。計算量は O(n) となり、非常に効率的な解法です。