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;
}