C++でバイナリ文字列に同じ文字が連続して含まれているかどうかを判定する方法

はじめに

0と1だけで構成されるバイナリ文字列が与えられたとき、その文字列の中に同じ文字が連続して出現する箇所があるかどうかを判定することを考えます。連続した同じ文字が存在する場合、その文字列は「無効」、存在しない場合は「有効」とみなします。

例えば、文字列 "101010" は隣り合う文字がすべて異なるため有効ですが、"10111010" には "11" という連続部分が含まれるため無効となります。

解決のアプローチ

この問題は非常にシンプルな手法で解決できます。文字列を左から右へ走査しながら、隣接する2つの文字を順番に比較していきます。一致するペアが1つでも見つかった時点で、連続する同じ文字が存在すると判断できます。

具体的な手順は以下の通りです。

• 文字列の先頭から末尾の1つ手前までループ処理を行う
• 各位置で現在の文字と次の文字を比較する
• 一致した場合は即座に false を返す（無効）
• 最後まで一致する箇所がなければ true を返す（有効）

C++での実装例

#include <iostream>
#include <algorithm>
using namespace std;
bool isConsecutiveSame(string str){
    int len = str.length();
    for(int i = 0; i<len - 1; i++){
       if(str[i] == str[i + 1])
       return false;
    }
    return true;
}
int main() {
    string str = "101010";
    if(isConsecutiveSame(str))
       cout << "No consecutive same characters";
    else
       cout << "Consecutive same characters found";
}

実行結果

No consecutive same characters

まとめ

このアルゴリズムは文字列を一度だけ走査すればよいため、時間計算量は O(n)、必要な追加メモリは O(1) と非常に効率的です。入力文字列の長さが大きくなっても線形時間で判定できるため、実用的な場面でも十分に活用できるアプローチといえます。