Pythonで隣接する異なるビットを削除した後の最短文字列の長さを求めるプログラム

2進文字列 s が与えられたとき、隣り合う2文字が異なる場合に限り、そのペアを削除できるものとします。この操作は何度でも繰り返し実行でき、最終的に得られる文字列のうち最も短くなるときの長さを求めるのがこの問題です。

例えば、入力が s = "1100011" の場合、答えは 1 になります。まず「10」を削除して「10011」にし、さらに「10」を削除して「011」とし、最後に「01」を削除すれば、残るのは「1」だけになるからです。

アプローチ:スタックを活用する

この問題は、スタック(stack)を使うことで効率的に解けます。手順は以下のとおりです。

• 新しいリスト(スタック)を用意します。
• 文字列 s 内の各文字 c について、次の処理を行います。
  • スタックが空、またはスタックの先頭の文字が c と同じ場合は、c をプッシュ(push)します。
  • スタックの先頭の文字が c と異なる場合は、スタックから要素をポップ(pop)します。
• 最後に、スタックに残っている要素数を返します。

このアルゴリズムがうまく機能するのは、隣接する異なる文字が出現するたびにペアとして即座に消去していくため、最後にスタックへ残るのは「これ以上削除できない同一文字の連なり」だけになるからです。

計算量

各文字を一度だけ走査するため、時間計算量は O(n) です。また、最悪の場合に文字列全体がスタックに積まれるため、空間計算量も O(n) となります。

Pythonでの実装例

class Solution:
   def solve(self, s):
      stack = []
      for c in s:
         if not stack or stack[-1] == c:
            stack.append(c)
         elif stack[-1] != c:
            stack.pop()
      return len(stack)

ob = Solution()
print(ob.solve("1100011"))

入力

"1100011"

出力

1