【C++】文字列内で最も長く連続して繰り返される文字を見つける方法

アルファベットからなる文字列が与えられます。この課題では、文字列の中で最も長く連続して繰り返されている文字を見つけます。具体的な例を通じて確認していきましょう。

入力例と出力例

入力: String[] = "abbbabbbbcdd"

出力: b

説明: この文字列において、最も長い連続シーケンスを持つのは文字「b」で、連続する「b」は4個です。

入力: String[] = "aabbcdeeeeed"

出力: e

説明: この文字列において、最も長い連続シーケンスを持つのは文字「e」で、連続する「e」は5個です。

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

• アルファベットの文字列は、文字配列 string1[] に格納します。

• 関数 maxRepeating(char str[], int n) は、文字列本体とそのサイズの2つの引数を受け取り、最も長く連続して繰り返される文字を返します。

• str[] を先頭の位置から末尾まで順番に走査します。

• str[i] と次の文字 str[i+1] が同一である場合、現在の連続カウント(maxC)をインクリメントします。

• 連続カウントがこれまでの最大値を上回った場合、その値を count に、該当する文字を repchar に保存します。

• 最終的な結果として repchar を返します。

C++実装例

#include <iostream>
#include <cstdio>

char maxRepeating(char str[], int n){
    int count = 0;
    char repchar = str[0];
    int maxC = 1;
    for (int i = 0; i < n; i++){
        if (str[i] == str[i+1] && i < n-1)
            maxC++;
        else{
            if (maxC > count){
                count = maxC;
                repchar = str[i];
            }
            maxC = 1;
        }
    }
    return repchar;
}

int main(){
    char string1[] = "aaabbaacccddef";
    int N = 14;
    printf("最大連続繰り返し文字: %c\n", maxRepeating(string1, N));
    return 0;
}

実行結果

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

最大連続繰り返し文字: a

処理のポイントと計算量

このアルゴリズムは、文字列を先頭から一度だけ走査すればよいため、時間計算量は O(n)、追加で必要な記憶域は O(1) という非常に効率的な設計になっています。隣接する文字が異なる箇所(連続区間の切り替わり)で、直前に続いた区間の長さを最大値と比較することで、最も長く繰り返された文字を漏れなく特定できます。ログデータの解析や圧縮処理(RLEなど)の基礎となる典型的な文字列走査のパターンなので、ぜひマスターしておきましょう。