Pythonで文字列にm個の連続した1または0が含まれているかを判定する方法

2進数のみで構成された文字列 s と整数値 m が与えられたとき、その文字列の中に m個連続した「1」 または m個連続した「0」 が含まれているかどうかを判定する問題を考えてみましょう。

たとえば、入力が s = "1110111000111"、m = 3 の場合、「000」という3つ連続した0や「111」という3つ連続した1が存在するため、出力は True になります。

解決のアプローチ

この問題は、文字列を先頭から順に走査しながら、連続する「0」と「1」の出現回数をそれぞれカウントすることで解決できます。具体的には以下の手順に従います。

• str_size := 文字列 s の長さ
• count_0 := 0、count_1 := 0（それぞれ連続する0と1のカウンタ）
• i を 0 から str_size - 2 まで繰り返す
  • s[i] が '0' の場合
    • count_1 := 0（1の連続が途切れたためリセット）
    • count_0 := count_0 + 1
  • それ以外の場合
    • count_0 := 0（0の連続が途切れたためリセット）
    • count_1 := count_1 + 1
  • count_0 が m と等しい、または count_1 が m と等しい場合
    • True を返す
• ループが完了しても条件を満たさなければ False を返す

この方法のポイントは、異なる文字が出現した時点でもう一方のカウンタをリセットすることで、「連続性」を正確に追跡できる点です。計算量は文字列を一度だけ走査するため O(n) となり、非常に効率的です。

実装例

それでは、実際のPythonコードを見てみましょう。

def solve(s, m):
    str_size = len(s)
    count_0 = 0
    count_1 = 0
    for i in range(0, str_size - 1):
        if (s[i] == '0'):
            count_1 = 0
            count_0 += 1
        else:
            count_0 = 0
            count_1 += 1
        if (count_0 == m or count_1 == m):
            return True
    return False

s = "1110111000111"
m = 3
print(solve(s, m))

入力

"1110111000111", 3

出力

True

コードの解説

このプログラムでは、関数 solve が文字列 s と目標回数 m を受け取ります。ループ内で現在の文字が '0' なら count_0 を増やして count_1 をリセットし、'1' ならその逆を行います。どちらかのカウンタが m に達した瞬間に True を即座に返すため、無駄な処理が発生しません。

なお、ループ範囲を str_size - 1 までとしているのは、最後の文字まで確実にチェック対象に含めるためです。もし最後の文字もチェックしたい場合は、range(0, str_size) とすることでより安全に動作させることができます。

この手法は、ログデータの解析やビットパターンの検出など、連続する同一要素の検出が必要なさまざまな場面で応用できる基本的かつ重要なテクニックです。