C++ Beats 100% || Explained with Example ||st
Intuition\n Describe your first thoughts on how to solve this problem. \nThere are 2 approaches two solve this problem by the DP & by Stack .\nHere we have used
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThere are 2 approaches two solve this problem by the DP & by Stack .\nHere we have used stack approach.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nExplain with an example:\ns = "(()())"\n\n1. Initial stack: [-1], maxL: 0\nwhy we intialise with -1?\n~ : Consider a case that s= "()" or any string with a valid paranthesis at the beginning, we want the gap between the previous invalid case, but if there is valid paranthesis at the beginning, there is no previous invalid case, to indicate that, we push -1 into the stack, here at index=1, max len = 1-(-1)=2\n\n2. i=0: s[0] = \'(\', push 0 onto stack: [-1, 0]\n\n3. i=1: s[1] = \'(\', push 1 onto stack: [-1, 0, 1]\n\n4. i=2: s[2] = \')\', pop from stack (1 is the top element), update maxL to 2 - (-1) = 3: [-1, 0]\n\n5. i=3: s[3] = \'(\', push 3 onto stack: [-1, 0, 3]\n6.i=4: s[4] = \')\', pop from stack (3 is the top element), update maxL to 4 - 0 = 4: [-1]\n\n6. i=5: s[5] = \')\', pop from stack (0 is the top element), update maxL to 5 - (-1) = 6: []\n\n7. Final maxL: 6 (length of the longest valid parentheses substring)\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N) As we have used stack and did push & pop operations simultaneoulsy.\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N) \n# Code\n```\nclass Solution {\npublic:\n    int longestValidParentheses(string s) {\n        stack<int> st;\n        st.push(-1);\n        int maxLen = 0;\n        for(int i=0; i<s.length(); i++) {\n            char ch = s[i];\n            if(ch == \'(\') {\n                st.push(i);\n            }\n            else {\n                st.pop();\n                if(st.empty()) {\n                    st.push(i);\n                }\n                else {\n                    int len = i - st.top();\n                    maxLen = max(len, maxLen);\n                }\n            }\n        }\n        return maxLen;\n    }\n};\n```
['Stack', 'C++']