Pythonで交互の並びを実現するために必要な最小フリップ回数を求めるプログラム

問題の概要

2進文字列 s が与えられているとします。この文字列に対しては、任意の接頭辞（先頭部分）を取り出して末尾へ移動するという操作が可能です。そのうえで、「隣り合う文字が同じ値にならないようにする」ために必要な最小の反転（フリップ）回数を求めるのがこの問題の目的です。

たとえば、入力が s = "10010101111" の場合を考えてみましょう。まず接頭辞「10」を末尾に移動すると、文字列は「01010111110」になります。さらに、右から3番目と5番目のビットを0に反転すれば「01010101010」となり、0と1が交互に並んだ状態が完成します。したがって、このケースの出力は 2 となります。

解法のアプローチ

この問題は、スライディングウィンドウ（尺取り法）を使うことで効率的に解けます。ポイントは次の通りです。

• 考えられるすべての回転（ローテーション）を網羅するため、文字列を2周分走査します。
• 各位置で、0と1が交互に並ぶ基準パターンとの不一致数をカウントします。
• パターンが「0」で始まるときの不一致数を s とすると、「1」で始まる場合は N − s になります。
• ウィンドウを1つずつずらしながら不一致数の最小値を更新し、最終的な答えを求めます。

アルゴリズムの手順

1. ans を S のサイズ、N を S のサイズとして初期化し、s を 0 に設定します。
2. i を 0 から 2×N−1 までループさせます。
3. s に int(S[i mod N] XOR (i AND 1)) を加算します。
4. i ≥ N − 1 のとき、ans を ans・s・N − s のうちの最小値で更新します。
5. 続けて、ウィンドウの左端に対応する値を s から減算し、ウィンドウを1つずらします。
6. ループ終了後、ans を返します。

実装例

以下はPythonによる実装例です。

class Solution:
    def solve(self, S):
        ans = N = len(S)
        s = 0
        for i in range(2 * N):
            s += int(S[i % N]) ^ (i & 1)
            if i >= N - 1:
                ans = min(ans, s, N - s)
                s -= int(S[(i - (N - 1)) % N]) ^ ((i - (N - 1)) & 1)
        return ans
ob = Solution()
s = "10010101111"
print(ob.solve(s))

入力

"10010101111"

出力

2

計算量

時間計算量は O(N)、空間計算量は O(1) です。文字列を2周分走査しますが、各ステップの処理は定数時間で済むため、非常に効率的なアルゴリズムになっています。