DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

Longest Valid Parentheses

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 ')'.

SOLUTION:

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        stack = [-1]
        mlen = 0
        for i, c in enumerate(s):
            if c == '(':
                stack.append(i)
            elif len(stack) > 0:
                stack.pop()
                if len(stack) > 0:
                    mlen = max(mlen, i - stack[-1])
                else:
                    stack.append(i)
        return mlen
Enter fullscreen mode Exit fullscreen mode

Top comments (0)