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 Explanation
Method 1: Use a stack to keep track of indices and update the maximum valid length each time. Method 2: Use dynamic programming where dp[i] represents the length of the longest valid substring ending at i, updating based on previous valid substrings.
Solution in C++
#include
#include
#include
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s; cin >> s;
int n = s.size(), ans = 0;
stack 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 << "
";
return 0;
}