Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
 
Example 1:
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:
Input: s = ""
Output: 0

 
Constraints:

0 <= s.length <= 3 * 104
s[i] is '(', or ')'.

Difficulty: interview

Starter code:

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        

Solutions:
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        memo ={}
        n =len(s)
        def dp(i):
            if i<=0:
                return 0
            if i in memo:
                return memo[i]
            if (s[i-1],s[i])==('(',')'):
                memo[i]=dp(i-2)+2
            elif (s[i-1],s[i])==(')',')') and i-dp(i-1)-1>=0 and s[i-dp(i-1)-1]=='(':
                memo[i]=dp(i-1)+2+dp(i-dp(i-1)-2)
            else:
                memo[i]=0
            return memo[i]
        ret = 0
        for i in range(n-1,0,-1):
            ret = max(ret, dp(i))
        return ret
            
            
            
            
        
        
        
            
            
                
        


class Solution:
    def longestValidParentheses(self, s: str) -> int:
        left = 0
        right = 0
        res = 0
        
        for c in s:
            if c =='(':
                left +=1
            if c == ')':
                right += 1
            if left == right:
                res = max(res, left+right)
            if right > left:
                left = 0
                right = 0
        
        left = 0
        right = 0
        for i in range(len(s)-1,-1, -1):
            c = s[i]
            if c =='(':
                left +=1
            if c == ')':
                right += 1
            if left == right:
                res = max(res, left+right)
            if left > right:
                left = 0
                right = 0
        
        return res