【Python】バイナリ文字列に「1」の連続セグメントが最大1つかどうかを判定するプログラム

問題の概要

先頭にゼロが付いていないバイナリ文字列 s が与えられます。この文字列に「1」の連続したセグメント(区間)が最大でも1つしか含まれていないかどうかを判定する必要があります。

たとえば、入力が s = "11100" の場合、「1」のセグメントは「111」の1つだけであるため、出力は True になります。一方、s = "110100" の場合は「11」と「1」という2つのセグメントが存在するため、出力は False となります。

解決のアプローチ

この問題は、次の手順で解くことができます。

• 変数 count を -1 に初期化します。
• s の長さが1の場合は True を返します。
• s の各文字 i について、次の処理を繰り返します。
  • i が「1」であり、かつ count > -1 の場合は False を返します。
  • そうではなく、i が「0」の場合は count を1増やします。
• ループが終了したら True を返します。

ここでのポイントは、count が「これまでに出現した0の個数 − 1」を表している点です。count が 0 以上になると、すでに少なくとも1つの「0」が出現済みであることを意味します。その状態で再び「1」が出現すると、それは2つ目の「1」のセグメントの始まりを示すため、即座に False を返せばよいのです。

実装例

def solve(s):
    count = -1
    if len(s) == 1:
        return True
    for i in s:
        if i == "1" and count > -1:
            return False
        elif i == "0":
            count += 1
    return True

s = "11100"
print(solve(s))

入力

11100

出力

True

計算量の分析

• 時間計算量: O(n) — 文字列を先頭から末尾まで一度だけ走査します。
• 空間計算量: O(1) — 追加の記憶領域として必要なのはカウンタ変数1つだけです。

別のシンプルな方法

Pythonでは、文字列操作を活用してより簡潔に書くこともできます。「1」で分割したときの要素数が2以下であれば、セグメントは最大1つだと判断できます。

def solve(s):
    return len(s.strip("0").split("1")) <= 2 if "1" in s else True

どちらの方法でも線形時間で正しく判定できますので、用途に応じて使い分けるとよいでしょう。