問題の説明：

'(' と ')' のみからなる文字列が与えられます。最長の有効な（形式が正しく連続している）括弧部分文字列の長さを見つけてください。

例 1：

入力：s = "(()"
出力：2
説明：最長の有効な括弧部分文字列は "()" です
例 2：

入力：s = ")()())"
出力：4
説明：最長の有効な括弧部分文字列は "()()" です
例 3：

入力：s = ""
出力：0

制約：

0 <= s.length <= 3 * 104
s[i] は '(' または ')' です

解法1：補助スタックによるアプローチ

考え方

1. スタックの役割：スタックはインデックスを格納します。走査中に、2つの連続するインデックスが括弧のペアを形成できる場合、スタックからポップします。これにより、スタックには現在の位置までで一時的に括弧を形成できないインデックスが格納されます。

2. どのような条件で現在の文字が括弧を形成できないのでしょうか？
   i. 現在のスタックが空です。現在の文字 s[i] がスタックの最初の文字になり、以前の文字と括弧を形成できなくなります
   ii. 現在の文字 s[i] が左括弧 '(' です。左括弧はスタックのトップ要素と括弧を形成できません
   iii. スタックのトップ要素が右括弧 ')' です。現在の文字 s[i] が何であれ、トップ要素と括弧を形成できません

つまり、スタックのトップ要素が '(' で、現在の文字 s[i] が ')' である場合にのみ括弧のペアを形成できます

3. 括弧のペアが形成された後、スタックのトップ要素をポップします。
   これにより、前述の「スタックには現在の位置までで一時的に括弧を形成できないインデックスが格納される」という条件が満たされます

4. 現在の有効な括弧の長さ = 現在のインデックス i - スタックに格納されたインデックス stack[-1]
   最終的に返す最長有効括弧の長さは res = max(res, i - stack[-1]) となります
   この時点でスタックが空の場合は、res = max(res, i - (-1)) となります

class ParenthesesAnalyzer:
    def find_longest_valid(self, expression: str) -> int:
        index_stack = []
        max_length = 0
        for position in range(len(expression)):
            if not index_stack or expression[position] == '(' or expression[index_stack[-1]] == ')':
                index_stack.append(position)
            else:
                index_stack.pop()
                current_length = position - (index_stack[-1] if index_stack else -1)
                max_length = max(max_length, current_length)
        return max_length

時間計算量：O(n)
空間計算量：O(n)

解法2：動的計画法によるアプローチ

class ParenthesesAnalyzer:
    def find_longest_valid(self, expression: str) -> int:        
        max_result = 0
        dp = [0] * len(expression)
        for i in range(len(expression)):
            if expression[i] == ")":
                # Pythonの負数インデックスを避けるため
                if i - 1 < 0: continue
                if expression[i - 1] == "(":
                    dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
                elif i - dp[i - 1] > 0 and expression[i - dp[i - 1] - 1] == "(":
                    dp[i] = dp[i - 1] + (dp[i - dp[i - 1] - 2] if i - dp[i - 1] >= 2 else 0) + 2
                max_result = max(max_result, dp[i])
        return max_result

時間計算量：O(n)
空間計算量：O(n)

解法3：0

時間計算量：O(n)
空間計算量：O(n)