Pythonでバイナリ文字列から「01」「10」を削除して最大スコアを求める方法

問題の概要

バイナリ文字列 s と、2つの整数値 zero_one および one_zero が与えられます。このとき、次のような操作を任意の回数だけ実行できるものとします。

• 部分文字列「01」を削除すると、zero_one ポイントを獲得できる
• 部分文字列「10」を削除すると、one_zero ポイントを獲得できる

操作を何度でも行える場合に、取得できるポイントの合計の最大値を求めるのがこの問題の目的です。

たとえば、入力が s = "10100101"、zero_one = 3、one_zero = 2 の場合、答えは 11 になります。「01」を3回削除して 3 × 3 = 9 ポイントを獲得し、残った文字列は「10」になります。これを削除すればさらに 2 ポイントが加わり、合計は 11 となるのです。

解法のアプローチ

この問題は、スタックを活用した貪欲法(グリーディ法)で効率的に解くことができます。手順は以下の通りです。

• 入力文字列をビットのリスト A に変換します
• もし zero_one < one_zero ならば、両者の値を入れ替え、A の各要素を XOR 1 で反転します。これにより、「01」の削除が常に高得点側になるように問題を正規化できます
• 答えを格納する変数 ans := 0 と初期化します
• 空のスタックを用意します
• A の各要素 x について以下を処理します
  • スタックが空でなく、スタックの先頭要素が x より小さい場合は、スタックからポップし、ans に zero_one を加算します(これは「01」パターンを検出して即座に削除することを意味します)
  • それ以外の場合は、x をスタックにプッシュします
• 最後に、ans に one_zero × min(スタック内の 0 の個数, スタック内の 1 の個数) を加算します。スタックに残った要素から作れる「10」ペアの数だけ追加スコアが得られるためです
• ans を返します

Pythonでの実装例

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

class Solution:
    def solve(self, S, zero_one, one_zero):
        A = list(map(int, S))
        if zero_one < one_zero:
            zero_one, one_zero = one_zero, zero_one
            for i in range(len(A)):
                A[i] ^= 1
        ans = 0
        stack = []
        for x in A:
            if stack and stack[-1] < x:
                stack.pop()
                ans += zero_one
            else:
                stack.append(x)
        ans += one_zero * min(stack.count(0), stack.count(1))
        return ans
ob = Solution()
s = "10100101"
zero_one = 3
one_zero = 2
print(ob.solve(s, zero_one, one_zero))

入力

"10100101", 3, 2

出力

11

計算量について

このアルゴリズムでは、各ビットがスタックにプッシュ・ポップされるのはそれぞれ高々1回なので、時間計算量は O(n)、空間計算量もスタックの分だけ O(n) となります。文字列が長くなっても高速に動作する、非常に効率的な解法です。