32. Longest Valid Parentheses

Problem Statement

link: https://leetcode.com/problems/longest-valid-parentheses/ https://leetcode.cn/problems/longest-valid-parentheses/

Given a string containing just the characters ‘(‘ and ‘)’, return the length of the longest valid (well-formed) parentheses substring.

Example:

Input: s = "(()" Output: 2

Input: s = ")()())" Output: 4

Input: s = "" Output: 0

Solution Approach

Use a stack to store indices, pushing for left parentheses and popping for right. Update results accordingly, marking unmatched right parentheses when the stack is empty.

Algorithm

1. Initialize a stack with -1 to serve as the base for counting valid lengths.
2. Traverse the string; push the index for ‘(‘ and pop for ‘)’, resetting the base if the stack is empty.
3. After each pop, calculate the length using the current index and the top of the stack to keep track of the longest valid parentheses.

Implement

    class Solution:
          def longestValidParentheses(self, s: str) -> int:
              stack = [-1]
              res = 0
              for i, c in enumerate(s):
                  if c == '(':
                      stack.append(i)
                  else:
                      stack.pop()
                      if not stack:
                          stack.append(i)
                      else:
                          res = max(res, i - stack[-1])
              return res

    
    

Twitter  facebook  Email