Pythonで1つの0を反転した後に得られる、連続する1の最長部分文字列の長さを求めるプログラム

バイナリ文字列 s が与えられたとします。「0」を「1」に反転できるのは最大1回までという条件のもとで、連続する「1」からなる最長の部分文字列の長さを求める必要があります。

例えば、入力が s = "1010110001" の場合、出力は 4 になります。インデックス3にある「0」を反転すると文字列は "1011110001" となり、このとき連続する「1」の最長部分文字列の長さが4になるためです。

解決アプローチ：スライディングウィンドウ

この問題はスライディングウィンドウ（2ポインタ）のテクニックを使うことで効率的に解けます。ウィンドウ内に含まれる「0」の数が1個以下である状態を保ちながら右端を伸ばし、条件を満たさなくなったら左端を縮めていくのがポイントです。

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

• n := 文字列 s の長さ
• ans := 0、ones := 0、left := 0、right := 0 で初期化
• right < n の間、以下を繰り返す：
  • s[right] が「1」なら、ones を1増やす
  • right - left + 1 - ones > 1（ウィンドウ内の「0」が2個以上ある状態）の間、以下を繰り返す：
    • remove := s[left]
    • remove が「1」なら、ones を1減らす
    • left を1増やす
  • ans := ans と (right - left + 1) の最大値
  • right を1増やす
• ans を返す

実装例

理解を深めるために、以下の実装例を見てみましょう。

def solve(s):
    n = len(s)
    ans = ones = left = right = 0
    while right < n:
        if s[right] == "1":
            ones += 1
        while right - left + 1 - ones > 1:
            remove = s[left]
            if remove == "1":
                ones -= 1
            left += 1
        ans = max(ans, right - left + 1)
        right += 1
    return ans

s = "1010110001"
print(solve(s))

入力

"1010110001"

出力

4

計算量について

各文字は左ポインタと右ポインタによってそれぞれ最大1回ずつ処理されるため、時間計算量は O(n)、追加のメモリ使用量は O(1) となります。文字列が非常に長い場合でも高速に動作するのがこの手法の大きな利点です。