Pythonで操作を繰り返した後に得られる最大のバイナリ文字列を求めるプログラム

ここでは、あるバイナリ文字列(0と1だけで構成された文字列)が与えられたとき、次の2種類の操作を何回でも適用できるものとして、最終的に得られる数値として最大のバイナリ文字列を求める方法を解説します。

• 文字列に部分文字列 "00" が含まれる場合、それを "10" に置き換えられる。
• 文字列に部分文字列 "10" が含まれる場合、それを "01" に置き換えられる。

問題の例

たとえば入力が s = "001100" の場合、出力は 111011 になります。実際には、次のように文字列を変形できます。

(00)1100 → 101(10)0 → 1010(10) → 10(10)01 → 100(10)1 → 1(00)011 → 111011

解法のアプローチ

この問題は、各ステップを以下のように整理することで効率的に解けます。

• length : 文字列 s の長さ
• zeros : s に含まれる '0' の個数
• zeros < 2 の場合、どの操作も数値を増やせないため、そのまま s を返す
• s の先頭にある連続する '1' を取り除く
• leading_ones : 取り除いた先頭の '1' の個数
• leading_ones に zeros - 1 を加算する(残りの 0 をほぼすべて 1 に変換できるため)
• trailing_ones : 残りの部分に含まれる '1' の個数(length - leading_ones - 1)
• answer_left : leading_ones 個の '1'
• answer_right : trailing_ones 個の '1'
• answer_left + "0" + answer_right を連結して返す

ポイントは、最終的な答えには 0 が最大でも 1 つしか残らないという点です。操作を組み合わせることで 0 を集めて 1 に変換でき、残った唯一の 0 は、先頭の 1 の並びの直後に配置するのが最適になります。

Pythonによる実装例

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

def solve(s):
    length = len(s)
    zeros = s.count('0')
    if zeros < 2:
        return s
    s = s.lstrip('1')
    leading_ones = length - len(s)
    leading_ones += zeros - 1
    trailing_ones = length - leading_ones - 1
    answer_left = '1' * leading_ones
    answer_right = '1' * trailing_ones
    return ''.join([answer_left, '0', answer_right])

s = "001100"
print(solve(s))

入力

"001100"

出力

111011

計算量について

このアルゴリズムは、文字列の走査とカウントのみで構成されているため、時間計算量は O(n)、空間計算量も結果の文字列生成を除けば O(1) です。文字列の長さが非常に大きい場合でも高速に動作します。