C++で隣接する重複文字を含まない最も近い文字列を出力する方法

問題概要

この問題では、1つの文字列が与えられます。私たちのタスクは、元の文字列に最も近く、かつ隣接する重複文字を一切含まない文字列を出力することです。

具体例を見てみましょう。

入力：string = "good"
出力：goad

この例では、インデックス1と2の文字が同じであるため、インデックス2の文字を変更しています。こうすることで「good」から最も近い形を保ちながら、隣接する重複を取り除いています。

解決アプローチ

この問題を解くには、文字列を走査しながら、隣接する2つの文字が同じかどうかを確認します。同じ場合は、後ろ側の文字（i番目とi+1番目が一致しているならi+1番目）を変更します。この解法では貪欲アルゴリズム（グリーディ法）を使用し、隣接して一致している各ペアに対して1回の変更を行います。

注意すべき点は、文字を変更する際に前後の要素をすべて確認することです。つまり、i番目の文字を変更する場合、変更後にi番目とi+1番目の文字が異なる状態になるようにしなければなりません。これを怠ると、修正の過程で新たな重複を作り出してしまう可能性があります。

アルゴリズムの手順

1. 文字列を先頭から順に走査します。
2. 現在の文字が直前の文字と一致した場合、その文字を一旦「a」に置き換えます。
3. 置き換えた文字が、前の文字とも次の文字とも一致しなくなるまで、1ずつ増やしていきます。
4. これを文字列の末尾まで繰り返し、最終的な結果を出力します。

実装例

上記の解法を実装したプログラムは以下の通りです。

#include <iostream>
#include <string.h>
using namespace std;
void printStringWithNoDuplicates(string str){
    int len = str.length();
    for (int i = 1; i < len; i++){
        if (str[i] == str[i - 1]){
            str[i] = 'a';
            while (str[i] == str[i - 1] || (i + 1 < len && str[i] == str[i + 1])) str[i]++;
            i++;
        }
    }
    cout<<str;
}
int main(){
    string str = "good";
    cout<<"元の文字列 : "<<str<<endl;
    cout<<"隣接する重複文字を含まない文字列 : ";
    printStringWithNoDuplicates(str);
    return 0;
}

出力結果

元の文字列 : good
隣接する重複文字を含まない文字列 : goad

まとめ

このように、貪欲法を用いて文字列を一度だけ走査することで、時間計算量O(n)で隣接する重複文字を含まない最も近い文字列を効率的に求めることができます。各位置での変更は必要最小限にとどめられるため、元の文字列からの変化も最小に抑えられます。英小文字のみで構成された文字列であれば、必ず26文字の中から前後と異なる文字を選べるため、この手法は常に有効です。