Longest Valid Parentheses in Python

Suppose we have a string, with opening and closing parentheses. We have to find the longest length of the valid (well-formed) parentheses. So if the input is like “))(())())”, then the result will be 6, as the valid string is “(())()”.

To solve this, we will follow these steps −

• Make a stack, and insert -1., set ans := 0

• for i in range 0 to length of stack – 1

  • if s[i] is opening parentheses, then insert i into stack

  • otherwise

    • if stack is not empty and top of stack is not -1 and s[stack top] is opening parentheses, then

      • top element from stack

      • ans := max of ans and i – stack top

    • otherwise insert i into stack

• return ans

Example

Let us see the following implementation to get a better understanding −

 Live Demo

class Solution(object):    def longestValidParentheses(self, s):       stack = [-1]       ans = 0       for i in range(len(s)):          if s[i] == "(":             stack.append(i)          else:             if stack and stack[-1]!=-1 and s[stack[-1]] == "(":                stack.pop()                ans = max(ans,i - stack[-1])             else:             stack.append(i)       return ans ob = Solution() print(ob.longestValidParentheses("))(())())"))

Input

"))(())())"

Output

6