Pythonでバイナリ文字列を2つに分割して最大スコアを求める方法

問題概要

バイナリ文字列 s が与えられているとします。ここで、文字列を2つの空でない部分文字列 s1 と s2 に分割する操作を考えます。この分割の「スコア」は、s1 に含まれる「0」の個数と、s2 に含まれる「1」の個数の合計として定義されます。目的は、この操作によって得られる最大のスコアを求めることです。

例えば、入力が s = "011001100111" の場合、出力は 8 になります。これは、文字列を "01100" + "110111" のように分割すると、左側に「0」が3個、右側に「1」が5個含まれるため、スコアは 3 + 5 = 8 となるからです。

解決のためのアプローチ

この問題は、文字列全体の「1」の個数を先に数えておき、左から順に分割位置を動かしながらスコアを更新していくことで効率的に解けます。具体的には、以下の手順に従います。

• ones := 文字列 s 全体に含まれる「1」の個数

• zeros := 0(左側部分に含まれる「0」の個数)

• ans := 0(最大スコアの初期値)

• i を 0 から s の長さ - 2 まで繰り返す(両方の部分文字列が空にならないよう、最後の1文字は必ず右側に残します)

  • s[i] が「0」と同じ場合:

    • zeros := zeros + 1

  • それ以外の場合:

    • ones := ones - 1

  • ans := ans と (ones + zeros) のうち大きい方

• ans を返す

このアルゴリズムの時間計算量は O(n)、空間計算量は O(1) であり、文字列を一度走査するだけで答えが求まるため非常に効率的です。

実装例

理解を深めるために、以下のPython実装を見てみましょう。

def solve(s):
   ones = s.count("1")
   zeros = 0
   ans = 0
   for i in range(len(s) - 1):
      if s[i] == "0":
         zeros += 1
      else:
         ones -= 1
      ans = max(ans, ones + zeros)
   return ans

s = "011001100111"
print(solve(s))

入力

"011001100111"

出力

8

まとめ

バイナリ文字列の分割による最大スコア問題は、「1」の総数を事前に把握し、分割位置を左から順に走査しながら「0」と「1」のカウントを更新していくだけで解決できます。線形時間 O(n) で処理できるため、長い文字列に対しても高速に動作する実用的なアルゴリズムです。