Unraveling the Mystery of Longest Valid Parentheses
Intuition\nThe intuition behind the given code is to use a stack to efficiently track the indices of opening parentheses.\n\n# Approach\n1. Initialize Variables
# Intuition\nThe intuition behind the given code is to use a stack to efficiently track the indices of opening parentheses.\n\n# Approach\n1. Initialize Variables: Initialize necessary variables such as n to store the size of the input string s, st as a stack to keep track of indices of opening parentheses, and maxx to store the maximum length of valid parentheses substring found so far.\n\n2. Base Index: Push -1 onto the stack initially. This serves as a base index and helps in calculating the length of valid substrings starting from the beginning of the string.\n\n3. Iterate Through String: Loop through each character of the input string s from index 0 to n-1.\n\n4. Handling Opening Parentheses: If the current character is an opening parenthesis \'(\', push its index onto the stack.\n\n5. Handling Closing Parentheses: If the current character is a closing parenthesis \')\', pop the top index from the stack. This indicates that the closing parenthesis matches with the nearest unmatched opening parenthesis.\n\n6. Calculate Length of Valid Substring: If the stack is not empty after popping an index, calculate the length of the valid parentheses substring ending at the current index by subtracting the current index from the index at the top of the stack.\n\n7. Update Maximum Length: Update the maximum length found so far (maxx) if the length of the current valid substring is greater than the previously recorded maximum length.\n\n8. Handling Unmatched Closing Parentheses: If the stack becomes empty after popping an index, it means the current closing parenthesis doesn\'t have a matching opening parenthesis. In such cases, push the current index onto the stack as a new base index.\n\n9. Return Maximum Length: After processing all characters in the string, return the maximum length found (maxx), which represents the length of the longest valid parentheses substring within the input string.\n\n# Complexity\n- Time complexity:\nO(N)\n\n- Space complexity:\nO(N)\n\n# Code\n```\nclass Solution {\npublic:\n    int longestValidParentheses(string s) {\n        int n=s.size();\n        stack<int>st;\n        //for () -1 act as an base index\n        st.push(-1);\n        int maxx=0;\n\n        for(int i=0;i<n;i++)\n        {\n            if(s[i]==\'(\')\n            {\n                st.push(i);\n            }\n            else\n            {\n                st.pop();\n                if(!st.empty())\n                {\n                    maxx=max(maxx,i-st.top());\n                }\n                else\n                {\n                    st.push(i);\n                }\n            }\n        }\n        return maxx;\n    }\n};\n```
['String', 'Stack', 'C++']