C++ easy solution with stack and Dynamic programming with explanation
We can solve this problem using stack. We will push -1 into the stack, so that whenever the stack becomes empty then we are sure that it is not valid at that po
We can solve this problem using stack. We will push -1 into the stack, so that whenever the stack becomes empty then we are sure that it is not valid at that point. So, whenever we have \')\' then we pop the element from the stack and if it is empty then the string ending at that index is not valid and we need to push the index so to find next valid parenthesis length. Let\'s do a dry run of the below code by using the string "()(()".\n\nFirst, we push -1 so initially stack element is -1.\nAt i=0, we have s[i]=\'(\' , we push the index 0.\nAt i=1, we have s[i]=\')\', we pop the element from the stack so the current valid length till index 1 becomes (i-stack.top()) i.e. (1-(-1))=2.\nAt i=2, we have s[i]=\')\' , we pop the element from the stack and note that stack now becomes empty so any new valid string would start after this index only. Thus, we push the index i=2 in the stack.\n\nAt i=3, we have s[i]=\'(\', we push the index 3 in the stack.\nAt i=4, we have s[i]=\')\', we pop the element and since the stack is still not empty, we find the length valid till this index as (4-2)=2.\n\nThus, the longest valid parenthesis length is 2 for this example.\nThe time complexity of this approach is O(n) and space complexity is also O(n).\n\nPlease let me know me in the comment section if you need further clarification on how this approach works.\n\n```\nclass Solution {\npublic:\n    int longestValidParentheses(string s) {\n        stack<int> p;\n        int maxlength=0;\n        p.push(-1);\n        for(int i=0;i<s.length();i++)\n        {\n            if(s[i]==\'(\')\n            {\n                p.push(i);\n            }\n            else{\n                p.pop();\n                if(p.empty())\n                    p.push(i);\n                else\n                    maxlength=max(maxlength,i-p.top());\n            }\n        }\n        return maxlength;\n    }\n};\n```\n\nWe can also use dynamic programming to solve this problem. We can find the length of valid parenthesis till each index.  For any string ending with \'(\' the length would be zero since valid parenthesis cannot end with \'(\'. \n\nIf the string ends with \')\', then there will be two cases :\n\n1. If the previous character is \'(\' then the length of valid parenthesis ending at this index would be dp[i-2] + 2.\n2.  We need to check if the character at (i-dp[i-1]-1) =\'(\' if it is the length of valid parenthesis ending at this point is dp[i-1] + (i>=2 ? dp[i-dp[i-1]-2] :0) +2.\n\n```\nclass Solution {\npublic:\n    int longestValidParentheses(string s) {\n       int maxlength=0;\n       vector<int> dp(s.length(),0);\n        for(int i=1;i<s.length();i++)\n        {\n            if(s[i]==\')\')\n            {\n                if(s[i]==\'(\')\n                    dp[i]=(i>=2 ? dp[i-2] : 0)+2;\n                else if(i-dp[i-1]-1>=0 && s[i-dp[i-1]-1]==\'(\')\n                    dp[i]=dp[i-1]+((i-dp[i-1])>=2 ? dp[i-dp[i-1]-2] :0)+2;\n            }\n            maxlength=max(maxlength,dp[i]);\n        }\n        return maxlength;\n    }\n};\n```
['Dynamic Programming', 'Stack', 'C', 'C++']