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 ')'.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Data structures

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