Pythonで解く「最長の有効な括弧」問題:スタックを使った効率的なアプローチ

問題概要

開き括弧と閉じ括弧で構成された文字列が与えられたとき、その中に含まれる最も長い「有効な(整形式の)」括弧列の長さを求める問題です。例えば、入力が "”))(())())"" の場合、有効な部分文字列は "“(())()"" となるため、答えは 6 になります。

アルゴリズム:スタックを利用した解法

この問題は、スタックを使うことで線形時間で効率的に解くことができます。手順は以下の通りです。

• スタックを作成し、初期値として -1 を挿入します。また、答えを格納する変数 ans を 0 で初期化します。
• i を 0 から文字列の長さ - 1 まで順に処理します。
  • s[i] が開き括弧 "(" の場合は、インデックス i をスタックにプッシュします。
  • それ以外の場合(閉じ括弧 ")" の場合):
    • スタックが空でなく、スタックの先頭が -1 ではなく、かつ s[スタックの先頭] が開き括弧であれば:
      • スタックの先頭要素をポップします。
      • ans を max(ans, i - スタックの先頭) で更新します。
    • それ以外の場合は、インデックス i をスタックにプッシュします。
• 最後に ans を返します。

ポイント:-1 の役割

スタックの底に置いた -1 は「基準点」として機能し、有効な括弧列の開始位置より一つ前のインデックスを表しています。対応する開き括弧がマッチした際に、現在の位置との差分を取ることで、有効な括弧列の長さを正確に計算できる仕組みです。

実装例

以下にPythonでの実装例を示します。

class Solution(object):
    def longestValidParentheses(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.longestValidParentheses("))(())())"))

入力

"))(())())"

出力

6

計算量の分析

• 時間計算量: O(n) — 文字列を一度だけ走査すればよいため、非常に効率的です。
• 空間計算量: O(n) — 最悪の場合(すべて開き括弧など)、全インデックスがスタックに積まれます。