C++で左右の隣接文字が同じである文字をカウントする方法

文字列（例えば str）が与えられ、その中から「左側と右側の隣接文字が同じである文字」の数を求めるのが課題です。なお、文字列の先頭と末尾の文字は隣接文字を1つしか持たないため、常にカウント対象に含めます。

具体例

入力 − string str = "poiot"
出力 − カウントは 3

説明 − この文字列では、先頭の「p」、末尾の「t」、そして左右の隣接文字がどちらも「o」である「i」が条件を満たすため、カウントは3になります。

入力 − string str = "nitihig"
出力 − カウントは 4

説明 − この文字列では、「n」「t」「h」「g」が条件を満たすため、カウントは4になります。

アルゴリズムの流れ

• 文字列を変数（例えば str）に入力として受け取ります。

• length() 関数を使って文字列の長さを取得します。この関数は空白を含む文字数を整数値として返します。

• 文字列の長さが2以下の場合は、すべての文字がカウント対象となるため、そのまま長さを返します。

• 長さが2より大きい場合は、カウントの初期値を2（先頭と末尾の文字分）に設定します。

• i を 1 から始め、i が (length − 1) 未満である間ループを回します。

• ループ内で str[i-1] == str[i+1] が成立する場合、つまり左右の隣接文字が同じであれば、カウントを1増やします。

• ループ終了後、カウントの合計値を返します。

• 結果を出力します。

実装例

#include <iostream>
using namespace std;
// 文字をカウントする関数
int countChar(string st){
    int size = st.length();
    if (size <= 2){
        return size;
    }
    int result = 2;
    // 文字列を走査する
    for (int i = 1; i < size - 1; i++){
        // 前後の文字が同じ場合はカウントを1増やす
        if (st[i - 1] == st[i + 1]){
            result++;
        }
    }
    // 結果を返す
    return result;
}
int main(){
    string st = "poiot";
    cout << "count is " << countChar(st);
    return 0;
}

出力結果

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

count is 3

このアルゴリズムの計算量は O(n) であり、文字列を一度だけ走査すればよいため、非常に効率的です。また、補助的なデータ構造を必要としないため、空間計算量は O(1) となります。