Pythonでバイナリ文字列を交互文字列にするために必要な最小の変更回数を求めるプログラム

問題の概要

バイナリ文字列 s が与えられます。1回の操作につき1つのビットを反転(0を1に、または1を0に)できるものとします。隣り合う2文字が同じにならない文字列は「交互文字列」と呼ばれます。このとき、s を交互文字列に変換するために必要な最小の操作回数を求めるのが本記事のテーマです。

たとえば、入力が s = "11100011" の場合、答えは 3 になります。位置 1、4、7 のビットを反転すると "10101010" となり、すべての隣接文字が異なる交互文字列が完成するためです。

解法のアプローチ

交互文字列は必ず次の2パターンのどちらかに一致します。

• パターンA: 偶数番目が '1'、奇数番目が '0'(例:"10101010")
• パターンB: 偶数番目が '0'、奇数番目が '1'(例:"01010101")

したがって、各位置の文字数を数えて、それぞれのパターンへ変換するのに必要な反転回数を求め、小さい方を採用すればよいことになります。

アルゴリズムの手順

• change := 0 で初期化する
• even_1 := 0、even_0 := 0(偶数インデックスにある '1' と '0' の個数)
• odd_1 := 0、odd_0 := 0(奇数インデックスにある '1' と '0' の個数)
• i を 0 から s の長さ - 1 まで繰り返す:
  • i が偶数の場合:s[i] が '1' なら even_1 を +1、そうでなければ even_0 を +1
  • i が奇数の場合:s[i] が '1' なら odd_1 を +1、そうでなければ odd_0 を +1
• (even_1 + odd_0) が (even_0 + odd_1) より大きければ、change := even_0 + odd_1
• そうでなければ、change := even_1 + odd_0
• change を返す

ポイントは、パターンB("0101...")に揃えるには偶数位置の '1'(even_1)と奇数位置の '0'(odd_0)を反転する必要があり、そのコストは even_1 + odd_0 となる点です。同様に、パターンA("1010...")に揃えるコストは even_0 + odd_1 です。この2つのうち小さい方こそが求める最小操作回数になります。

Pythonでの実装例

以下のコードで実際の動作を確認できます。

def solve(s):
    change = 0
    even_1 = 0
    even_0 = 0
    odd_1 = 0
    odd_0 = 0
    for i in range(len(s)):
        if(i % 2 == 0):
            if(s[i] == '1'):
                even_1 += 1
            else:
                even_0 += 1
        else:
            if(s[i] == '1'):
                odd_1 += 1
            else:
                odd_0 += 1
    if((even_1 + odd_0) > (even_0 + odd_1)):
        change = even_0 + odd_1
    else:
        change = even_1 + odd_0
    return change

s = "11100011"
print(solve(s))

入力

"11100011"

出力

3

計算量について

このアルゴリズムは文字列を一度だけ走査するため、時間計算量は O(n) です。また、使用するのはカウンタ変数のみなので、空間計算量も O(1) に抑えられます。長いバイナリ文字列に対しても非常に効率的に動作する点が魅力です。