Given : A string containing ‘(’ and ‘)’ characters.
Objective : To find the length of the longest valid parentheses substring.
Example :
1. In the string " ( ( ) ( " the longest valid parentheses substring is " ( ( ) ( " of length 2.
2. In the string " ( ) ( ) ( ( ) ( " the longest valid parentheses substring is " ( ) ( ) ( ( ) ( " of length 4.
C++ : Program to find the longest valid parentheses substring
#include<iostream>
#include<string>
#include<stack>
#include<vector>
using namespace std;
int Length_LongestValid_Parentheses (string str) {
stack<int> stk;
stk.push(-1);
int maxlen = 0;
for (int index=0; index < str.size(); index++) {
if (str.at(index) == '(') {
stk.push(index);
} else if (str.at(index) == ')') {
stk.pop();
if (stk.empty()) {
stk.push(index);
} else {
if (maxlen < index - stk.top()) {
maxlen = index - stk.top();
}
}
}
}
return maxlen;
}
int main() {
vector<string> vec = {"((()", "()()()", "()(()", "))())", "(", "(((())))()(()()()"};
for (const auto& str : vec) {
cout << "String : " << str << endl;
cout << "Length of longest valid parantheses : " << Length_LongestValid_Parentheses(str) << endl << endl;
}
return 0;
}
Output
String : ((()
Length of longest valid parantheses : 2
String : ()()()
Length of longest valid parantheses : 6
String : ()(()
Length of longest valid parantheses : 2
String : ))())
Length of longest valid parantheses : 2
String : (
Length of longest valid parantheses : 0
String : (((())))()(()()()
Length of longest valid parantheses : 10