Pythonで文字列を正しい括弧列にするために削除が必要な括弧の最小数を求めるプログラム

括弧のみで構成された文字列が与えられたとき、その文字列を「正しい括弧列」(すべての開き括弧が必ず対応する閉じ括弧と一致する状態)にするために削除すべき括弧の最小数を求める関数をPythonで作成します。

例えば、入力が "(()))(" の場合、出力は 2 になります。これは、正しい文字列 "(())" を得るために余分な ")(" の2文字を削除する必要があるためです。

解法のアプローチ

この問題は、文字列を一度走査するだけで効率的に解くことができます。具体的には、以下の手順に従います。

• カウンタ total と temp をそれぞれ 0 で初期化する
• 文字列 s 内の各文字 p について、次の処理を行う
  • p が "(" の場合:
    • total := total + 1(未対応の開き括弧としてカウント)
  • p が ")" かつ total が 0 でない場合:
    • total := total − 1(対応する開き括弧が見つかったので相殺)
  • それ以外の場合:
    • temp := temp + 1(対応する開き括弧がない余分な閉じ括弧としてカウント)
• 最後に total + temp を返す

アルゴリズムのポイント

変数 total は、走査の終了時点でまだ対応する閉じ括弧が見つかっていない開き括弧の残数を表します。一方、temp は、対応する開き括弧が存在しない余分な閉じ括弧の数を記録します。この2つの合計が、まさに削除すべき括弧の最小数となります。

この手法の計算量は、時間計算量 O(n)、空間計算量 O(1) であり、非常に効率的です。

それでは、理解を深めるために実際の実装例を見てみましょう。

実装例(Pythonコード)

class Solution:
    def solve(self, s):
        total = 0
        temp = 0
        for p in s:
            if p == "(":
                total += 1
            elif p == ")" and total:
                total -= 1
            else:
                temp += 1
        return total + temp

ob1 = Solution()
string = "(()))("
print(ob1.solve(string))

入力

"(()))("

出力

2

まとめ

この問題は、貪欲法(Greedy)的な発想で1回の走査により解決できる典型的な例です。開き括弧と閉じ括弧の対応関係をリアルタイムに追跡することで、不要な括弧の数を正確に特定できます。同様の考え方は、括弧の妥当性チェックやスタックを使う関連問題にも応用できるため、ぜひマスターしておきましょう。