Pythonで3つ以上連続する同一ビットを解消する最小操作回数を求めるプログラム

問題概要

2進文字列 s が与えられます。ここで「任意の1ビットを選び、その値を 0 → 1、または 1 → 0 へ反転する」という操作を考えます。この操作を繰り返して、3つ以上の同一ビットが連続しない文字列を作るとき、必要な最小操作回数を求めるのが本記事のテーマです。

入力例

s = "10011100" の場合、答えは 1 になります。たとえばインデックス4(0始まり)の「1」を「0」に反転すれば "10010100" となり、3つ以上連続する同一ビットは存在しなくなります。

解法の考え方

ポイントは、文字列を「同じビットが連続している区間(ラン)」ごとに分割して考えることです。長さ n のランの中で3連続を避けるためには、少なくとも ⌊n ÷ 3⌋ 回の反転が必要です。

• 長さ3のラン("111")→ 1回の反転で対応可能("110" など)
• 長さ5のラン("11111")→ 1回の反転で対応可能("11011" など)
• 長さ6のラン("111111")→ 2回の反転が必要("110110" など)

したがって、各ランの長さを3で割った商(小数点以下切り捨て)をすべて合計したものが答えになります。

アルゴリズムの手順

• l := 0、count := 0 で初期化する
• l が s の長さ未満である間、次を繰り返す
  • r := l とする
  • r が s の長さ未満 かつ s[r] が s[l] と等しい間、r を1ずつ増やす
  • count := count + ⌊(r − l) ÷ 3⌋
  • l := r とする
• count を返す

Pythonでの実装例

def solve(s):
    l = 0
    count = 0
    while l < len(s):
        r = l
        # 同じビットが続く限り r を進める
        while r < len(s) and s[r] == s[l]:
            r += 1
        # ランの長さを3で割った商だけ反転が必要
        count += (r - l) // 3
        l = r
    return count

s = "10011100"
print(solve(s))

入力

"10011100"

出力

1

計算量

• 時間計算量:O(n) — 文字列を一度走査するだけ
• 空間計算量:O(1) — 追加のメモリは定数

まとめ

連続する同一ビットの「ラン」に着目し、各ランの長さを3で割った商の総和を取るだけで、最小反転回数を効率よく求められます。シンプルな貪欲的な発想で解ける、良い学習例題といえるでしょう。