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 : 2

Explanation : ()

Input: )()())

Output : 4

Explanation: ()()

Input: ()(()))))

Output: 6

Explanation: ()(())

**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…