# Longest valid parentheses challenge

**Problem statement**

Given a string containing just the characters `(`

and `)`

, find the length of the longest valid (well-formed) parentheses substring.

**Sample input**

(()

**Sample output**

2

**Sample input 1**

)()())

**Sample output 1**

4

**Solution**

We will solve this problem using a Stack. We are going to iterate over the input string `s`

using an index `i`

and push index `i`

on the stack. While we iterate, we will check the letter positioned at the index contained on top of the stack (`stack.peek()`

). If `s[stack.peek()]`

is the letter `(`

and the current character is `)`

we will *pop* the top of the stack. We will keep *popping* as long as the later is true.

Once we iterated over all the letters in the input string the stack can either be empty or contain those indices for which we couldn’t find a counterpart parenthesis. For example, if we consider the input `)()())`

, the stack will contain the index `0`

and `5`

at the end of the iteration.

In case the stack isn’t empty we will iterate over all indices contained in the stack and keep track of the maximum *distance* between two adjacent indices, since this distance represents the length of a valid (well-formed) parentheses substring. We then return the maximum distance.

In case the stack is empty, we know that the entire input string is a well-formed parentheses string and return the length of that string.

**Full code**

class Stack: def __init__(self): self.items = [] def isEmpty(self): return self.items == [] def push(self, item): self.items.append(item) def pop(self): return self.items.pop() def peek(self): return self.items[len(self.items)-1] def size(self): return len(self.items) def __str__(self): return ",".join([str(element) for element in self.items]) class Solution(object): def longestValidParentheses(self, s): """ :type s: str :rtype: int """ ans = 0 stack = Stack() i = 0 while i < len(s): while i < len(s) and s[i] == ')' and (not stack.isEmpty() and s[stack.peek()] == '('): stack.pop() i += 1 if i < len(s): stack.push(i) i += 1 if stack.isEmpty(): return len(s) b = len(s) while not stack.isEmpty(): a = stack.pop() ans = max(ans, b - a - 1) b = a ans = max(ans, b) return ans def main(): solution = Solution() print(solution.longestValidParentheses(")()())")) # 4 print(solution.longestValidParentheses("(()")) # 2 print(solution.longestValidParentheses("()")) # 2 print(solution.longestValidParentheses("())")) # 2 if __name__ == "__main__": main()