Python DP + stack - very easy to understand (Beats 99.52%)
Simply iterate through the string.\nIf s[i] == "(" simply store the position in the stack, and dp[i] = 0 (because it does not signify the end of any valid paren
Simply iterate through the string.\nIf `s[i] == "("` simply store the position in the stack, and `dp[i] = 0` (because it does not signify the end of any valid parentheses. The position in stack will be used to check if the string made is completed or not later.\nNow, if `s[i] == ")"` see if the length of stack > 0, if it is not, `dp[i] = 0` because no valid parentheses end there. if length > 0, then pop the top of the stack, that is the position of the `"("` that completes the current `")"`. \nNow, just check if there was any valid parentheses ending just before that position. Because, if there was, this should be added to our length of the valid parentheses.\neg:\n`()(())`\n`dp = [0, 2, 0, 0, 2, 6]`\nHere, for the last `)` at position 5, it gets completed by the `(` at position 2, now check position 1, if there is a valid parentheses ending there, add its length to the current length.\n\nThe code is below:\n\n```\n def longestValidParentheses(self, s):\n        """\n        :type s: str\n        :rtype: int\n        """\n        if not s:\n            return 0\n        \n        stack = []\n        dp = [0]*len(s)\n        \n        for i in range(len(s)):\n            if s[i] == "(":\n                stack.append(i)\n                dp[i] = 0\n            else: #we have a closing brace\n                if len(stack) == 0:\n                    dp[i] = 0\n                else:\n                    pos = stack.pop()\n                    dp[i] = dp[pos-1]+i-pos+1\n        return max(dp)\n```\n
[]