Zenn
🎯

【Python】Longest Valid Parentheses（括弧の最大長）

2025/04/13に公開
Python
tech

初めに

こんにちは！アルゴリズムの問題でスタックを使用する問題について解説していこうと思います！

問題

文字列sが与えられます。
この文字列は '(' と ')' からなり、正しく閉じた括弧列のうち、最長の長さを返してください。

入力例

  • 入力: s = "(()"
  • 出力: 2（"()" が最長）
  • 入力: s = ")()())"
  • 出力: 出力: 4（"()()" が最長）
  • 入力: s = ""
  • 出力: 0

解説

問題の本質

この問題の本質は「開き括弧 ( と閉じ括弧 ) が対応して正しく閉じられた部分列のうち、最長の長さを求める」です。

そもそもスタックとは？

後入れ先出し (LIFO: Last-In, First-Out) の原則に基づいて要素を管理するアルゴリズムです。例えるなら、本の積み重ね。一番上に積んだ本が一番最初に取り出されるイメージです。

この問題のアプローチ

  1. まず「数字（インデックス）」をスタックに入れる
    なぜ数字（位置）を入れるの？
    →括弧が閉じたときに「どこからどこまでが正しいか」を数字で数えるため！

  2. 最初に -1 をスタックに入れておく
    最初から () があるとき、ちゃんと長さを数えるために必要！

  3. '(' が来たらインデックスを積む

  4. ')' が来たらスタックから1つポップ

    • スタックが空なら、今の位置を基準に追加
    • スタックが空でなければ、「今の位置 - スタックの一番上」で長さ計算

実装してみる

def longest_valid_parentheses(s: str) -> int:
    stack = [-1]  # 最初の基準点
    max_len = 0   # 一番長い長さを保存する

    for i, char in enumerate(s):
        if char == '(':# 開き括弧はとりあえずスタックに入れる
            stack.append(i)
        else:  # char == ')'
            # 閉じ括弧が来たら、1つ前の開き括弧を取り出す（＝対応づけ）
            stack.pop()
            if not stack:
                stack.append(i)# スタックが空になったら基準点を更新
            else:
                length = i - stack[-1]# 長さ = 今の位置 - スタックの一番上
                max_len = max(max_len, length)

    return max_len


print(longest_valid_parentheses("(()"))        
print(longest_valid_parentheses(")()())"))    
print(longest_valid_parentheses(""))          
print(longest_valid_parentheses("((()))"))

実行結果
2
4
0
6

少し実況してみる　例: ) ( ) ( ) )

  1. 初期状態
    スタック: [-1] ← 最初の基準点
    max長さ: 0

  2. 位置0 → ) （右かっこ）
    右かっこが最初に来たから… スタックから1つ出す！→空になる→ 位置0をスタックに入れる
    スタック: [0]
    max長さ: 0

  3. 位置1 → ( （左かっこ）
    左かっこが来たら、位置をスタックに積む!
    スタック: [0, 1]
    max長さ: 0

  4. 位置2 → ) （右かっこ）
    ペアができる！ → スタックから1つ出す
    スタック: [0]
    長さ = 2 - 0 = 2
    max長さ: 2

  5. 位置3 → ( （左かっこ）
    左かっこ → スタックに積む
    スタック: [0, 3]
    max長さ: 2

  6. 位置4 → ) （右かっこ）
    ペアができる！ → スタックから1つ出す
    スタック: [0]
    長さ = 4 - 0 = 4
    max長さ: 4

  7. 位置5 → ) （右かっこ）
    右かっこ → スタックから1つ出す
    スタック: [] → 空になった！
    位置5をスタックに入れる → [5]
    max長さ: 4

  8. 最終結果
    最長は４となる。

Discussion