C言語で文字列内の同一文字間の最大文字数を求める方法

問題の概要

アルファベットで構成された文字列が与えられ、その中には同じ文字が少なくとも2回以上出現しているものとします。この課題の目的は、任意の文字について、その2つの出現位置の間に存在する文字数の最大値を求めることです。もし一つも文字の重複が存在しない場合は、-1 を返します。

入力 − 文字列 str = "abcdba"

出力 − 文字列内の同一文字間の最大文字数 − 4

説明 − 繰り返し現れる文字は「a」と「b」のみで、それぞれのインデックスは以下の通りです −

1. 'a' 最初のインデックス 0、最後のインデックス 5 → 間の文字数は 5-0-1=4
2. 'b' 最初のインデックス 1、最後のインデックス 4 → 間の文字数は 4-1-1=2
　　繰り返し文字間の最大文字数：4

入力 − 文字列 str = "AbcAaBcbC"

出力 − 文字列内の同一文字間の最大文字数 − 5

説明 − 繰り返し現れる文字は「A」「b」「c」で、それぞれのインデックスは以下の通りです −

1. 'A' 最初のインデックス 0、最後のインデックス 3 → 間の文字数は 3-0-1=2
2. 'b' 最初のインデックス 1、最後のインデックス 7 → 間の文字数は 7-1-1=5
3. 'c' 最初のインデックス 2、最後のインデックス 6 → 間の文字数は 6-2-1=3
　　繰り返し文字間の最大文字数：5

注意 − 入力文字列が "abcdefg" のように重複する文字を一切含まない場合は、関数は -1 を返します。

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

• 文字列を格納するための文字配列 Str[] を用意します。

• maxChars(char str[], int n) 関数を使って、同一文字の出現位置間の最大文字数を計算します。

• 結果を格納する変数 maxC を -1 で初期化します。

• 外側のforループで、文字列配列を先頭から順番に走査します。

• ネストされたforループで残りの文字を走査し、重複が存在するかどうかを確認します（if (str[i] == str[j])）。

• 条件が真であれば、インデックス同士の差分を計算して間の文字数を求めます（temp = j-i-1）。

• この値がこれまでに見つかった最大値よりも大きければ、maxC に格納します。

• 文字列全体の走査が完了したら、maxC を返します。

計算量について

このアプローチでは二重ループを使用しているため、時間計算量は O(n²) となります。より効率化したい場合は、各文字の最初の出現位置と最後の出現位置を事前に記録しておき、一度の走査（O(n)）で差分を求める手法も有効です。

コード例

#include <stdio.h>
#include <math.h>
int maxChars(char str[],int n){
    int size = n;
    int maxC = -1;
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
            if (str[i] == str[j]){
                int temp=abs(j-i-1);
                maxC = maxC>temp?maxC:temp;
            }
    return maxC;
}
// ドライバーコード
int main(){
    char Str[] = "AbcAaBcbC";
    printf("Maximum number of characters between any two same character in a string :%d",
    maxChars(Str,9) );
    return 0;
}

実行結果

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

Maximum number of characters between any two same character in a string : 5