If we are given a string consisting of opening and closing parenthesis, let us find the
length of longest valid parenthesis-substring.
Examples:
Input : ((()
Output : 2
Explanation : ()
Input: )()())
Output : 4
Explanation: ()()
Input: ()(()))))
Output: 6
Explanation: ()(())
The Solution:
A Simple way is to find all substrings of the given string. For every given string, check if
it is a valid string or if it is not. If the string is valid and length is more than the
maximum length so far, then we update maximum length. We can check whether the substring is
valid or not valid in linear time using the stack. The time complexity of this solution is
O(n2).
An Easy & Efficient Solution can solve this problem in O(n) time. The idea is to store
indexes of the previous starting brackets in the stack. The first element of the stack is a
special element that provides index before the beginning of a valid substring (base for next
valid string).
- Create an empty stack & push -1 to it. The first element of the stack is used to provide
the base for next valid string.
- Initialize result as 0.
- If the character is '(' i.e. str[i] == '('), push index 'i' to the stack.
- Else (if the character is ')')
- Pop an item from the stack (Most of the time an opening bracket)
- If the stack is not empty, then find the length of a current valid substring by taking
the difference b/w the current index & top of the stack. If current length is more
than the result, then update the result.
- If the stack is empty, push current index as the base for next valid substring.
- Return result.
Below is the implementation of the above algorithm in C++
The Preprocessors:
#include < bits/stdc++.h >
using namespace std;
The Length Finding Function:
int findMaxLen(string str)
{
int n = str.length();
// Create stack & push -1 as initial index to it.
stack< int > stk;
stk.push(-1);
// Initialize result
int result = 0;
// Traverse all characters of given string
for (int i=0; i < n; i++)
{
// If opening bracket, push index of it
if (str[i] == '(')
stk.push(i);
else // If closing bracket, i.e.,str[i] = ')'
{
// Pop the previous opening bracket's index
stk.pop();
// Check if this length formed with
// base of current valid substring is
// more than max so far
if (!stk.empty())
result = max(result, i - stk.top());
// If stack is empty. push current index as
// base for next valid substring (if any)
else stk.push(i);
}
}
return result;
}
Main Function:
int main()
{
string str = "((()()";
cout << findMaxLen(str) << endl;
str = "()(()))))";
cout << findMaxLen(str) << endl ;
return 0;
}
Output:
