IPL 2021 - Final

IPL 2021 Finals are here and it is between the most successful team of the IPL Mumbai Indians and the team striving to garb their first trophy Royal Challengers Banglore. Rohit Sharma, captain of the team Mumbai Indians has the most experience in IPL finals, he feels lucky if he solves a programming question before the IPL finals. So, he asked the team’s head coach Mahela Jayawardene for a question. Question is, given a string S consisting only of opening and closing parenthesis ‘ie ‘(‘ and ‘)’, the task is to find out the length of the longest valid parentheses substring.

NOTE: The length of the smallest valid substring ( ) is 2.

• Time : O(n)
• Space : O(n)

class Solution {
public:
    int findMaxLen(string s) {
        vector<int> st{-1};
        int n = s.length(), res = 0;
        
        for(int i = 0; i < n; i++) {
            if(s[i] == '(')
                st.push_back(i);
            else {
                if(st.back() != -1 and s[st.back()] == '(') {
                    st.pop_back();
                    res = max(res, i - st.back());
                } else st.push_back(i);
            }
        }
        
        return res;
    }
};