Pythonで文字列内の最長の有効な括弧の長さを求めるプログラム

文字列 s が与えられます。この文字列は開き括弧「(」と閉じ括弧「)」のみで構成されています。ここで求めたいのは、最も長い有効（整形式）な括弧の部分文字列の長さです。

例えば、入力が ")(())())" の場合、最も長い有効な部分文字列は "(())()" であるため、結果は 6 となります。

アルゴリズムの考え方：スタックを活用する

この問題は、スタックを使うことで効率的に解くことができます。基本的なアイデアは、括弧の対応関係をスタックで管理し、マッチするたびに現在位置との差分から有効な長さを計算するというものです。

解法の手順

1. スタックを作成し、初期値として -1 を挿入します。また、答えを格納する変数 ans を 0 で初期化します。
2. i を 0 から文字列の長さ - 1 までループさせます。
   • s[i] が開き括弧「(」の場合：
     i をスタックにプッシュします。
   • s[i] が閉じ括弧「)」の場合：
     • スタックが空でなく、スタックの先頭が -1 ではなく、かつ s[stack[-1]] が開き括弧「(」である場合：
       • スタックの先頭要素をポップします。
       • ans = max(ans, i - stack[-1]) として、これまでの最大値を更新します。
     • それ以外の場合：
       i をスタックにプッシュします（新しい区切りの基準点として記録）。
3. ループ終了後、ans を返します。

スタックの先頭には常に「直近の無効な位置（基準点）」が保持されるため、閉じ括弧がマッチしたタイミングで i - stack[-1] を計算すれば、その時点での有効な括弧列の長さが求まります。

実装例

以下にPythonによる実装を示します。

class Solution(object):
    def solve(self, s):
        stack = [-1]
        ans = 0
        for i in range(len(s)):
            if s[i] == "(":
                stack.append(i)
            else:
                if stack and stack[-1] != -1 and s[stack[-1]] == "(":
                    stack.pop()
                    ans = max(ans, i - stack[-1])
                else:
                    stack.append(i)
        return ans

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

入力

")(())())"

出力

6

計算量について

このアルゴリズムでは、各文字を一度だけ走査し、スタックへのプッシュ・ポップはそれぞれ O(1) で行えるため、時間計算量は O(n)、空間計算量も O(n) となります。動的計画法や両方向からの走査を用いる解法もありますが、スタックを使ったこの方法は実装がシンプルで理解しやすいのが特徴です。