✅Beats 💯%  TIME & 💯% SPACE C++ STACK BASED DEAD EASY APPROACH & CODE
Intuition\nStack to Keep Track of Opening Parentheses: The code uses a stack to keep track of the indices of opening parentheses \'(\' encountered while iterati
# Intuition\nStack to Keep Track of Opening Parentheses: The code uses a stack to keep track of the indices of opening parentheses \'(\' encountered while iterating through the input string.\n\nMatching Parentheses: When a closing parenthesis \')\' is encountered, it checks if there is a matching opening parenthesis \'(\' in the stack. If found, it marks both the opening and closing parentheses as valid by replacing them with underscores (\'_\'). This step essentially eliminates valid pairs of parentheses from further consideration.\n\nConsecutive Underscores Counting: After processing the entire string, it goes through the modified string with underscores (\'_\'). It counts consecutive underscores to determine the length of valid parentheses substrings. The idea is that consecutive underscores represent a sequence of valid parentheses.\n\nTracking the Longest Valid Substring: While counting consecutive underscores, it keeps track of the maximum count encountered, which corresponds to the length of the longest valid parentheses substring.\n\n# Approach\nInitialize variables:\n\nn is set to the length of the input string s.\nCreate an empty stack of integers named st. This stack will be used to store the indices of opening parentheses \'(\'.\nLoop through each character in the input string s using a for loop.\n\nInside the loop, check if the current character is a closing parenthesis \')\' (i.e., s[i] == \')\').\n\na. If it\'s a closing parenthesis and the stack st is not empty, it means there is a matching opening parenthesis \'(\' for the current closing parenthesis.\n\nb. Pop the top index j from the stack st, indicating that the opening parenthesis \'(\' at index j matches the closing parenthesis \')\' at index i.\n\nc. Replace both the opening and closing parentheses with underscores (\'_\') in the string s to mark them as valid and ignore them in subsequent calculations.\n\nIf the current character is an opening parenthesis \'(\' (i.e., s[i] == \'(\'), push its index i onto the stack st to keep track of unmatched opening parentheses.\n\nAfter processing the entire string s, all valid parentheses pairs should be marked with underscores (\'_\') in the string.\n\nInitialize a variable ans to 0. This variable will store the length of the longest valid parentheses substring.\n\nIterate through the modified string s using a for loop.\n\nWhen you encounter an underscore (\'_\'), it indicates a valid parentheses pair. Start counting consecutive underscores to determine the length of this valid parentheses substring.\n\na. Increment a counter variable ct by 1 for the current underscore.\n\nb. Use a while loop to count consecutive underscores by incrementing ct until a non-underscore character is encountered.\n\nc. After counting the consecutive underscores, update the loop variable i to the position after the last underscore.\n\nd. Update the ans variable by taking the maximum of its current value and the value of ct. This keeps track of the longest valid parentheses substring encountered so far.\n\nAfter processing the entire modified string s, the ans variable will contain the length of the longest valid parentheses substring.\n\nReturn the ans as the result.\n\n# Complexity\n- Time complexity:\nO(2*n) -> O(n)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n    int longestValidParentheses(string s) {\n        int n = s.length();\n    stack<int> st;\n    for(int i=0;i<n;i++)\n    {\n        if(s[i] == \')\')\n        {\n            if(st.empty()==0)\n            {\n                int j = st.top();\n                st.pop();\n                s[i] = \'_\';\n                s[j] = \'_\';\n            }\n        }\n        if(s[i] == \'(\')\n        {\n            st.push(i);\n        }\n    }\n    int ans = 0;\n    for(int i=0;i<n;i++)\n    {\n        if(s[i] == \'_\')\n        {\n            int ct=1;\n            i++;\n            while(s[i] == \'_\')\n            {\n                ct++;\n                i++;\n            }\n            i--;\n            ans = max(ans,ct);\n        }\n    }\n    return ans;\n    }\n};\n```
['C++']