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

Machine Learning Projects

Table of Contents

Question

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

Example 1:

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:

Input: s = ""
Output: 0

Constraints:

  • 0 <= s.length <= 3 * 104
  • s[i] is '(', or ')'.

Python Solution

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        max_len = 0
        for p in range(len(s)):
            if s[p] == '(':
                stack.append(p)
            else:
                stack.pop()
                if stack == []:
                    stack.append(p)
                else:
                    max_len = max(p-stack[-1],max_len)
        return(max_len)

Leave a Comment

Your email address will not be published.