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
4Explanation
"(())" 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…
