Pythonで最大1組の文字を入れ替えた後に得られる最長の連続する「1」を見つける方法

問題概要

0と1だけで構成される2進文字列 s が与えられます。文字列の中で最大1組の文字を入れ替えることができるとき、その操作によって得られる最も長い連続した「1」の部分文字列の長さを求めるのが目標です。

たとえば、入力が s = "1111011111" の場合、出力は 9 になります。s[4] の「0」と s[9] の「1」を入れ替えることで、「1」が9個連続する並びを作れるためです。

解法の考え方：スライディングウィンドウ

この問題はスライディングウィンドウ（尺取り法）を使うことで、線形時間で効率的に解くことができます。

基本となるアイデアは次のとおりです。

• ウィンドウ内に含まれる「0」の個数が最大1個となるよう、左右の境界を管理します。
• 「0」が1個以下であれば、その「0」をウィンドウの外側にある「1」と入れ替えることで、ウィンドウ全体を「1」で埋めることが可能だからです。

アルゴリズムの手順

1. 左端 l = 0、ウィンドウ内の「0」の個数 cnt = 0、答え ans = 0 で初期化します。
2. 右端 r を 0 から文字列の末尾まで順に動かします。
3. s[r] が「0」なら cnt を 1 増やします。
4. cnt が 1 を超えたら、ウィンドウの左端を縮めます。s[l] が「0」なら cnt を 1 減らし、l を 1 進めます。
5. 各ステップで ans = max(ans, r - l + 1) により最長の長さを更新します。
6. 最終的に、ans と文字列中に実際に存在する「1」の総数のうち小さい方を返します。

なぜ最後に「1」の総数と比較するのか

入れ替え操作では「1」の総数そのものを増やすことはできません。たとえば s = "1110111" のように「0」が1個だけ含まれる場合、ウィンドウは文字列全体（長さ7）をカバーできますが、実際に存在する「1」は6個しかありません。そこで min(ans, s.count("1")) とすることで、このようなケースでも正しい答えが得られます。

Pythonでの実装例

class Solution:
    def solve(self, s):
        l = 0
        cnt = 0
        ans = 0
        for r in range(len(s)):
            cnt += s[r] == "0"
            if cnt > 1:
                cnt -= s[l] == "0"
                l += 1
            ans = max(ans, r - l + 1)
        return min(ans, s.count("1"))

ob = Solution()
s = "1111011111"
print(ob.solve(s))

入力

"1111011111"

出力

9

計算量

• 時間計算量：O(n) — 左右のポインタはそれぞれ最大でも文字列の長さ分しか移動しません。
• 空間計算量：O(1) — 追加のデータ構造は不要です。