Pythonですべての1をグループ化するために必要な最小スワップ回数を求めるプログラム

問題の概要

0と1だけで構成される2進文字列が与えられ、任意の2つのビットを入れ替える（スワップする）ことができるとします。このとき、すべての「1」を連続した一つのグループにまとめるために必要な最小スワップ回数を求めるのが目的です。

例えば、入力が s = "0111001" の場合、出力は 1 になります。次のように、たった1回のスワップで達成できるからです。

0111001 → 1111000

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

この問題は「スライディングウィンドウ」の考え方を使うと効率的に解けます。ポイントは次の通りです。

• まず文字列中の「1」の総数を数えます。これを one とします。
• すべての1を集めるには、長さ one のウィンドウを文字列上で滑らせながら、「そのウィンドウ内にすでに含まれている1の数」が最大になる位置を見つけます。
• 必要なスワップ回数は「1の総数 − ウィンドウ内の1の数」となります。ウィンドウ外にある1を、ウィンドウ内の0の位置へ移動させる回数に相当するためです。

ウィンドウ内の1の数を高速に求めるために、累積和（プレフィックスサム）配列を使用します。

アルゴリズムの手順

1. 与えられた2進文字列から、0と1の整数リスト data を作成します。
2. one := 0、n := data の長さとします。
3. サイズ n の配列 summ を作り、0で初期化します。summ[0] := data[0] とします。
4. one := one + data[0] とします。
5. i を 1 から n−1 まで繰り返します。
   • summ[i] := summ[i−1] + data[i]（累積和を構築）
   • one := one + data[i]
6. ans := one とします。
7. left := 0、right := one − 1 とします。
8. right < n の間、以下を繰り返します。
   • left が 0 の場合は temp := summ[right]、それ以外の場合は temp := summ[right] − summ[left−1]（ウィンドウ内の1の個数）
   • ans := min(ans, one − temp)
   • right と left をそれぞれ 1 増やします。
9. ans を返します。

このアルゴリズムの計算量は、時間・空間ともに O(n) であり、文字列の長さに対して線形時間で処理できます。

Pythonでの実装例

以下の実装を見ると、より理解が深まるでしょう。

class Solution(object):
    def solve(self, s):
        data = list(map(int, list(s)))
        one = 0
        n = len(data)
        summ=[0 for i in range(n)]
        summ[0] = data[0]
        one += data[0]
        for i in range(1,n):
            summ[i] += summ[i-1]+data[i]
            one += data[i]
        ans = one
        left = 0
        right = one-1
        while right <n:
            if left == 0:
                temp = summ[right]
            else:
                temp = summ[right] - summ[left-1]
            ans = min(ans,one-temp)
            right+=1
            left+=1
        return ans
ob = Solution()
s = "0111001"
print(ob.solve(s))

入力

"0111001"

出力

1

まとめ

本記事では、2進文字列内のすべての1を連続したグループにまとめるために必要な最小スワップ回数を求める問題を扱いました。累積和とスライディングウィンドウを組み合わせることで、O(n) の効率的な計算量で解ける点がこの手法の大きな魅力です。同様のテクニックは、部分配列の合計や最大要素数を扱うさまざまなアルゴリズム問題にも応用できます。