Pythonでバイナリ文字列を並べ替えて0と1が交互に並ぶようにできるか判定する方法

問題の概要

長さ2以上のバイナリ文字列 s が与えられたとき、その文字列を並べ替えることで、0と1が交互に並んだ文字列（オルタネート文字列）を作れるかどうかを判定する問題です。

例えば、入力が s = "1000111" の場合、「1」が4個、「0」が3個含まれているため、これらを並べ替えて "1010101" を作ることができます。したがって、出力は True になります。

解法の考え方

0と1が交互に並ぶ文字列では、文字列の長さによって「0」と「1」の出現回数の関係が一意に決まります。

• 長さが偶数の場合：「0」と「1」の出現回数は必ず等しくなります（例："0101" → 0が2個、1が2個）。
• 長さが奇数の場合：どちらか一方の文字が、もう一方よりちょうど1個多くなります（例："10101" → 1が3個、0が2個）。

この性質を利用すると、実際に並べ替えを試みる必要はなく、各文字の出現回数を数えるだけで判定できます。手順は以下の通りです。

1. 文字列 s 内の「1」の出現回数（one_count）を数えます。
2. 文字列 s 内の「0」の出現回数（zero_count）を数えます。
3. s の長さが偶数の場合：one_count と zero_count が一致すれば True、そうでなければ False を返します。
4. s の長さが奇数の場合：|one_count − zero_count| が 1 であれば True、そうでなければ False を返します。

実装例

以下はPythonによる実装例です。str.count() メソッドを使うことで、各文字の出現回数を簡単に取得できます。

def solve(s):
    one_count = s.count('1')
    zero_count = s.count('0')
    if len(s) % 2 == 0:
        return (one_count == zero_count)
    return abs(one_count - zero_count) == 1

s = "1000111"
print(solve(s))

入力

"1000111"

出力

True

計算量の評価

このアルゴリズムは、文字列を一度走査して各文字の出現回数を数えるだけなので、時間計算量は O(n)、追加の記憶領域は O(1) で済みます（n は文字列の長さ）。文字列の長さが大きくなっても効率的に動作する点が魅力です。