C++で同じ文字が隣接しないように文字列を再配置する方法

任意の長さの文字列 str が与えられたとします。この課題では、結果として得られる文字列の中に同じ文字が隣り合って現れないように、与えられた文字列を再配置することを目指します。

入出力シナリオの例

入力 − string str = "itinn"

出力 − 隣接する2文字が同じにならないように文字を再配置した結果：initn

説明 − 文字列型の変数 str が与えられています。入力文字列に含まれる「nn」のように同じ文字が隣り合っている部分を入れ替えるなど、同じ文字が連続しないように文字を再配置します。その結果、最終的な文字列は「initn」になります。

入力 − string str = "abbaabbaa"

出力 − 隣接する2文字が同じにならないように文字を再配置した結果：ababababa

説明 − 文字列型の変数 str が与えられています。「bb」「aa」「bb」「aa」のように同じ文字が隣り合っている部分をすべて入れ替え、全体を通じて同じ文字が隣接しないように再配置します。最終的な文字列は「ababababa」になります。

アルゴリズムのポイント

この問題を解くうえでの鍵は、最も出現回数の多い文字から先に偶数番目（0, 2, 4, ...）へ配置することです。これにより、頻度の高い文字同士が隣接するリスクを最小限に抑えられます。また、ある1文字の出現回数が (文字列の長さ + 1) / 2 を超える場合、どのように並べ替えても同じ文字が隣接してしまうため、その時点で再配置不可能と判断できます。アルゴリズム全体の計算量は文字数を n とすると O(n) です。

本プログラムで採用しているアプローチ

• string 型の変数（str）に入力を受け取り、文字列の長さを計算して変数 length に格納します。

• length が 0 の場合は処理を中断して戻ります。

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

• 関数 Rearrangement(arr, length) 内部の処理は以下のとおりです。

  • (length + 1) / 2 によって文字列の基準サイズ size を求めます。

  • 各文字の出現回数を格納する vector<int> 型変数 vec(26, 0)、および string 型の ptr(length, ' ') を宣言し、整数型の一時変数 temp を 0 で初期化します。

  • for ループで str を走査し、vec[it - 'a']++ によって各小文字の出現回数をカウントします。

  • char 型変数 ch を作成し、maximum(vec) 関数の呼び出し結果を格納します。

  • 整数型変数 total を宣言し、vec[ch - 'a'] の値を設定します。

  • total が size より大きい場合、再配置が不可能であるため空文字列を返します。

  • while ループで total が 0 になるまで、ptr[temp] に ch を代入し、temp を 2 ずつ増加させ、total を 1 ずつ減らします。

  • vec[ch - 'a'] を 0 に設定します。続いて i を 0 から 26 未満まで for ループで走査し、vec[i] が 0 より大きい間、temp が length 以上になったら temp を 1 に切り替えて ptr[temp] に 'a' + i を代入し、temp を 2 ずつ増加させ、vec[i] を 1 ずつ減らします。

  • ptr を返します。

• 関数 char maximum(const vector<int>& vec) 内部の処理は以下のとおりです。

  • 整数型変数 high を 0 で初期化し、char 型変数 c を宣言します。

  • i を 0 から 26 未満まで for ループで走査し、vec[i] が high より大きい場合は high に vec[i] を、c に 'a' + i を設定します。

  • c を返します。

• 結果を出力します。

例

#include <bits/stdc++.h>
using namespace std;
char maximum(const vector<int>& vec){
    int high = 0;
    char c;
    for(int i = 0; i < 26; i++){
        if(vec[i] > high){
            high = vec[i];
            c = 'a' + i;
        }
    }
    return c;
}
string Rearrangement(string str, int length){
    int size = (length + 1) / 2;
    vector<int> vec(26, 0);
    string ptr(length, ' ');
    int temp = 0;
    for(auto it : str){
        vec[it - 'a']++;
    }
    char ch = maximum(vec);
    int total = vec[ch - 'a'];
    if(total > size){
        return "";
    }
    while(total){
        ptr[temp] = ch;
        temp = temp + 2;
        total--;
    }
    vec[ch - 'a'] = 0;
    for(int i = 0; i < 26; i++){
        while (vec[i] > 0){
            temp = (temp >= length) ? 1 : temp;
            ptr[temp] = 'a' + i;
            temp = temp + 2;
            vec[i]--;
        }
    }
    return ptr;
}
int main(){
    string str = "itinn";
    int length = str.length();
    if(length == 0){
        cout<<"Please enter a valid string";
    }
    string count = Rearrangement(str, length);
    if(count == ""){
        cout<<"Please enter a valid string";
    }
    else{
        cout<<"Rearrangement of characters in a string such that no two adjacent are same is: "<<count;
    }
    return 0;
}

出力

上記のコードを実行すると、以下のような出力が得られます。

Rearrangement of characters in a string such that no two adjacent are same is: initn