Longest Valid Parentheses || Simple code || Easy to understand ||Explained !!
There are different approaches to solve this problem.\nApproach -1: Using Stacks -\nThe main idea is pretty straight forward, we only update the result (res) wh
There are different approaches to solve this problem.\n**Approach -1: Using Stacks** -\nThe main idea is pretty straight forward, **we only update the result (res) when we find a valid paranthesis.**\n-> If we find a valid pair. We pop this pair and check gap between the current and previous invalid and update the res.\n```\nFor example: s= "())(())", stack= [-1 ], res =0, here the answer must be 4, the longest valid paranthesis is from index 3 to 6. So, lets dry run this example.\n    ->index 0 :  s[i] == \'(\'   push into stack,  //stack=[-1,0], res=0\n    ->index 1 :  s[i] == \')\'   we pop it out and see what\'s before "(". In this example it\'s -1. So the gap is "current_index - (-1) = 2"  // res = 2, stack = [-1]\n    ->index 2 :  s[i] == \')\'   we pop -1 the stack, here stack is empty, i.e, it is not a valid pair, so we push current index into stack      //res=2, stack = [2]\n    ->index-3 :  s[i] == \'(\'  we push into stack. // res =2, stack = [2,3]\n    ->index-4 :  s[i] == \'(\'  we push into stack. //res =2, stack = [2,3,4]\n    ->index-5 :  s[i] == \')\'  we pop the stack, update the res, gap = "current index - 3 = 2"     //res =2, stack = [2,3]\n    ->index-6 :  s[i] == \')\'  we pop the stack, update the res, gap = "current index - 2 =4"   //res = max(res,4 ) = 4, stack = [2]\n```\nHere we intially pushed \'-1\' to stack to cover all edge cases.\nHope this example helps in understanding the logic. Go through the code for better idea.\n\n```\nint longestValidParentheses(string s) {\n        stack<int>st;\n        st.push(-1);\n        int res =0;\n        for(int i=0;i<s.length();i++){\n            if(s[i]==\'(\')  st.push(i);\n            else{\n                st.pop();\n                if(st.empty()) st.push(i);\n                else res = max(res,i-st.top());\n            }\n        }\n        return res;\n    }\n```\n\n\n**Approach-2: Dynamic programming**:\nThe main idea is for every index of our DP array, dp[i], it stores the longest length of valid parentheses which is end at i, and the logic is :\n```\n\n-> If s[i] is \'(\',  dp[i] = 0,because any string end with \'(\' cannot be a valid paranthesis.\n-> else if s[i] is \')\', we have two conditions,\n  \t\t -> s[i-1] is \'(\', dp[i] = dp[i-2] + 2\n         -> s[i-1] is \')\' and s[i-dp[i-1]-1] == \'(\', dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]\n```\nBasically, we are finding the longest valid paranthesis ending at `index i`.\n\n```\nint longestValidParentheses(string s) {\n        if(s.length() <= 1) return 0;\n        int res = 0;\n        vector<int> dp(s.length(),0);\n        for(int i=1; i<s.length(); i++){\n            if(s[i] == \')\' && i-dp[i-1]-1 >= 0 && s[i-dp[i-1]-1] == \'(\'){\n                if(i-dp[i-1]-2 >=0) \n                    dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2];\n                else \n                    dp[i] = dp[i-1] + 2;\n                res = max(dp[i],res);\n            }\n        }\n        return res;\n    }\n```\n**Do Upvote if you like the explanation and find it helpful!!!**\n\nAny other ways to solve this problems ?? Thoughts?? Comment down below !!\n\n
['Dynamic Programming']