Python Easy 2 approaches - Space O(n) and O(1)
The time complexity for both the approaches is O(len(s).\n\n 1. ##### Space - O(len(s))\n\nThis approach solves the problem in similar way as https://leetcode.c
The time complexity for both the approaches is `O(len(s)`.\n\n 1. ##### **Space - O(len(s))**\n\nThis approach solves the problem in similar way as https://leetcode.com/problems/valid-parentheses/ using `Stack`. The stack is used to track indices of `(`. So whenever we hit a `)`, we pop the pair from stack and update the length of valid substring.\n\n```\nclass Solution:\n    def longestValidParentheses(self, s: str) -> int:\n        max_length = 0\n        stck=[-1] # initialize with a start index\n        for i in range(len(s)):\n            if s[i] == \'(\':\n                stck.append(i)\n            else:\n                stck.pop()\n                if not stck: # if popped -1, add a new start index\n                    stck.append(i)\n                else:\n                    max_length=max(max_length, i-stck[-1]) # update the length of the valid substring\n        return max_length\n```\n\n2. ##### **Space - O(1)**\nThe valid parantheses problem can also be solved using a counter variable. Below implementation modifies this approach a bit and uses two counters:`left` and `right` for `(` and `)` respectively. \n\nThe pseudo code for this approach:\n1. Increment `left` on hitting `(`.\n2. Increment `right` on hitting `)`.\n3. If `left=right`, then calculate the current substring length and update the `max_length`\n4. If `right>left`, then it means it\'s an invalid substring. So reset both `left` and `right` to `0`.\n\nPerform the above algorithm once on original `s` and then on the reversed `s`.\n\n```\nclass Solution:\n    def longestValidParentheses(self, s: str) -> int:\n        max_length = 0\n                \n        l,r=0,0        \n        # traverse the string from left to right\n        for i in range(len(s)):\n            if s[i] == \'(\':\n                l+=1\n            else:\n                r+=1                        \n            if l == r:# valid balanced parantheses substring \n                max_length=max(max_length, l*2)\n            elif r>l: # invalid case as \')\' is more\n                l=r=0\n        \n        l,r=0,0        \n        # traverse the string from right to left\n        for i in range(len(s)-1,-1,-1):\n            if s[i] == \'(\':\n                l+=1\n            else:\n                r+=1            \n            if l == r:# valid balanced parantheses substring \n                max_length=max(max_length, l*2)\n            elif l>r: # invalid case as \'(\' is more\n                l=r=0\n        return max_length\n```\n\n---\n\n***Please upvote if you find it useful***
['Python', 'Python3']