Pythonでバイナリ文字列の1を最小スワップ回数でグループ化するアルゴリズム

問題の概要

0と1だけで構成されたバイナリ文字列 input_str が与えられます。目標は、隣接する文字同士しか入れ替えられないという制限のもとで、すべての「1」を連続した一つのグループにまとめることです。そのために必要な最小スワップ回数を求めて返します。

たとえば、入力が input_str = '10110101' の場合、答えは 4 になります。実際の入れ替えの流れは次のとおりです。

10110101 → 01110101 → 01111001 → 01111010 → 01111100

合計スワップ回数は 4 回です。

解法の考え方：中央値を基準に1を集める

この問題は中央値(median)の考え方を使うと効率的に解けます。数直線上の複数の点を1か所に集めるとき、移動距離の合計が最小になる集合位置は平均値ではなく中央値だからです。外れ値の影響を受けず、全体の移動コストを均等に分散できる点がポイントです。

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

• one := 文字列の中で「1」が出現する位置(インデックス)のリストを作成する
• mid := リスト one の長さを 2 で割った商(中央の要素を指すインデックス)
• res := 0(スワップ回数の合計)
• i を 0 から one の長さ未満まで繰り返す:
  • res := res + |one[mid] − one[i]| − |mid − i|
• res が 0 未満なら 0 を返し、そうでなければ res を返す

ここで |one[mid] − one[i]| は「i 番目の1から中央の1までの現在の距離」、|mid − i| は「グループ化後の整列状態で本来埋まるべきずれ幅」を表します。両者の差を合計することで、各1を中央へ寄せるのに必要なスワップ回数が求まります。

Pythonでの実装例

def solve(input_string):
    one = [i for i in range(len(input_string)) if input_string[i] == '1']
    mid = len(one) // 2
    res = 0
    for i in range(len(one)):
        res += abs(one[mid] - one[i]) - abs(mid - i)
    return 0 if res < 0 else res

print(solve('10110101'))

入力

'10110101'

出力

4

計算量

• 時間計算量:O(n) — 文字列を一度走査して1の位置を収集し、再度ループで合計を計算するだけです。
• 空間計算量:O(k) — k は文字列に含まれる1の個数で、位置リストを保存する分だけ必要です。