Problem 33: Longest Valid Parentheses
Problem Statement: Given a string consisting only of '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Input
A single line containing the parentheses string.
Output
Print the length of the longest valid parentheses substring.
Examples
Input:
(()
Output:
2
Solution in C++
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s; cin >> s;
int n = s.size(), ans = 0;
stack<int> st;
st.push(-1);
for (int i = 0; i < n; i++){
if(s[i]=='(')
st.push(i);
else {
st.pop();
if(st.empty()) st.push(i);
else ans = max(ans, i - st.top());
}
}
cout << ans << "\n";
return 0;
}