# Find the longest sequence of multiple Parentheses

Problem statement: Given a string `s` consisting of open and closed brackets `"("` and `")"`, return the length of the longest substring in `s` that is a valid string of parentheses.

# Example 1

Input

`s = ")(())(()"`

Output

`4`

Explanation

`"(())"` is the longest substring with valid parentheses.

Naive approach: Find all the substrings of a given string. For every string, check if it is a valid string or not. If valid and length is more than maximum length so far, then update maximum length. We can check whether a substring is valid or not in linear time using a stack. Time complexity of this solution is O(n^2).

Efficient Solution: can solve this problem in O(n) time. The idea is to store indexes of previous starting brackets in a stack. The first element of the stack is a special element that provides index before the beginning of valid substring (base for next valid string).

Examples:

`Input : ((()Output : 2Explanation : ()Input: )()())Output : 4Explanation: ()() Input:  ()(()))))Output: 6Explanation:  ()(())`

Algorithm:

`1) Create an empty stack and push -1 to it.    The first element of the stack is used    to provide a base for the next valid string. 2) Initialize result as 0.3) If the character is '(' i.e. str[i] == '('),    push index'i' to the stack.    2) Else (if the character is ')')   a) Pop an item from the stack (Most of the       time an opening bracket)   b) If the stack is not empty, then find the      length of current valid substring by taking       the difference between the current index and      top of the stack. If current length is more       than the result, then update the result.   c) If the stack is empty, push the current index      as a base for the next valid substring.3) Return result.`

Python Code:

`def paranthese_sequence(string):     n = len(string)       # Create a stack and push -1     # as initial index to it.     stk = []     stk.append(-1)       # Initialize result     result = 0      # Traverse all characters of given string     for i in xrange(n):           # If opening bracket, push index of it         if…`