Given a string S consisting of opening and closing parenthesis '(' and ')'. Find length of the longest valid parenthesis substring.
A parenthesis string is valid if:
	For every opening parenthesis, there is a closing parenthesis.
	Opening parenthesis must be closed in the correct order.
Example 1:
Input: S = ((()
Output: 2
Explaination: The longest valid 
parenthesis substring is "()".
Example 2:
Input: S = )()())
Output: 4
Explaination: The longest valid 
parenthesis substring is "()()".
Your Task:
You do not need to read input or print anything. Your task is to complete the function maxLength() which takes string S as input parameter and returns the length of the maximum valid parenthesis substring.
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(|S|)
Constraints:
1 ≤ |S| ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Data structures

Starter code: # User function Template for Python3



class Solution:

    def maxLength(self, S):

        # code here

Solutions:
class Solution:

	def maxLength(self, S):
		stack = []
		max_length = 0
		start_index = 0
		for i in range(len(S)):
			if S[i] == '(':
				stack.append(i)
			elif not stack:
				start_index = i + 1
			else:
				stack.pop()
				if not stack:
					max_length = max(max_length, i - start_index + 1)
				else:
					max_length = max(max_length, i - stack[-1])
		return max_length


class Solution:

	def maxLength(self, S):
		stack = []
		ans = 0
		for i in range(len(S)):
			if S[i] == '(':
				stack.append(i)
			elif len(stack) != 0 and S[stack[-1]] == '(':
				stack.pop()
				if len(stack) == 0:
					l = i + 1
				else:
					l = i - stack[-1]
				ans = max(ans, l)
			else:
				stack.append(i)
		return ans


class Solution:

	def maxLength(self, S):
		count = 0
		stack = [-1]
		bracket = [')']
		traverse = -20
		for i in range(len(S)):
			if S[i] == '(':
				count += 1
				stack.append(i)
				bracket.append(S[i])
			else:
				if bracket[-1] == '(':
					stack.pop()
					bracket.pop()
				else:
					stack.append(i)
					bracket.append(S[i])
				count -= 1
			if count < 0:
				count = 0
				pass
			else:
				traverse = max(i - stack[-1], traverse)
		return traverse


class Solution:

	def maxLength(self, s):
		stack = [-1]
		max_length = 0
		for i in range(len(s)):
			if s[i] == '(':
				stack.append(i)
			else:
				stack.pop()
				if len(stack) == 0:
					stack.append(i)
				else:
					max_length = max(i - stack[-1], max_length)
		return max_length


class Solution:

	def maxLength(self, S):
		lefts = []
		ans = 0
		contin = [False] * len(S)
		for i in range(len(S)):
			if S[i] == '(':
				lefts.append(i)
			if S[i] == ')' and len(lefts) > 0:
				contin[lefts.pop()] = True
				contin[i] = True
		c = 0
		for i in range(len(S)):
			if not contin[i]:
				ans = max(c, ans)
				c = 0
				continue
			c += 1
		ans = max(c, ans)
		return ans


class Solution:

	def maxLength(self, S):
		l = 0
		r = 0
		maxcount = 0
		for i in range(len(S)):
			if S[i] == '(':
				l += 1
			else:
				r += 1
			if l == r:
				maxcount = max(maxcount, 2 * r)
			elif r > l:
				r = 0
				l = 0
		l = 0
		r = 0
		for i in range(len(S) - 1, -1, -1):
			if S[i] == '(':
				l += 1
			else:
				r += 1
			if l == r:
				maxcount = max(maxcount, 2 * l)
			elif r < l:
				r = 0
				l = 0
		return maxcount


class Solution:

	def maxLength(self, S):
		st = []
		st.append(-1)
		result = 0
		for i in range(len(S)):
			if S[i] == '(':
				st.append(i)
			else:
				if len(st) != 0:
					st.pop()
				if len(st) != 0:
					result = max(result, i - st[len(st) - 1])
				else:
					st.append(i)
		return result


class Solution:

	def maxLength(self, S):
		stack = []
		stack.append(-1)
		lengthCounter = 0
		for i in range(len(S)):
			if S[i] == ')':
				if len(stack) > 0:
					stack.pop()
					if len(stack) > 0:
						lengthCounter = max(lengthCounter, i - stack[-1])
					else:
						stack.append(i)
			else:
				stack.append(i)
		return lengthCounter


class Solution:

	def maxLength(self, S):
		n = len(S)
		stack = [(-1, ')')]
		answer = 0
		for i in range(n):
			if S[i] == '(':
				stack.append((i, S[i]))
			elif stack and stack[-1][1] == '(':
				stack.pop()
				answer = max(answer, i - stack[-1][0])
			else:
				stack.append((i, S[i]))
		return answer


class Solution:

	def maxLength(self, string):
		n = len(string)
		stk = []
		stk.append(-1)
		result = 0
		for i in range(n):
			if string[i] == '(':
				stk.append(i)
			else:
				if len(stk) != 0:
					stk.pop()
				if len(stk) != 0:
					result = max(result, i - stk[len(stk) - 1])
				else:
					stk.append(i)
		return result


class Solution:

	def maxLength(self, S):
		(top, stack) = (-1, [])
		T = [None] * len(S)
		for i in range(len(S)):
			if S[i] == '(':
				stack.append([S[i], i])
				top += 1
			elif top != -1:
				(T[i], T[stack[-1][1]]) = (True, True)
				stack.pop(-1)
				top -= 1
		(max_, count) = (0, 0)
		for t in T:
			if t:
				count += 1
			else:
				max_ = max(count, max_)
				count = 0
		return max(max_, count)


class Solution:

	def maxLength(self, S):
		if not S:
			return 0
		stack = [-1]
		ml = 0
		for (i, ch) in enumerate(S):
			if ch == '(':
				stack.append(i)
			else:
				stack.pop()
				if not stack:
					stack.append(i)
				else:
					c = i - stack[len(stack) - 1]
					ml = max(c, ml)
		return ml


class Solution:

	def maxLength(self, pars):
		n = len(pars)
		dp = [0] * n
		for (i, p) in enumerate(pars):
			if p == ')' and i - dp[i - 1] >= 1 and (pars[i - dp[i - 1] - 1] == '('):
				dp[i] = dp[i - 1] + 2 + (dp[i - dp[i - 1] - 2] if i - dp[i - 1] >= 2 else 0)
		return max(dp)


class Solution:

	def maxLength(self, S):
		s = S
		stack = [-1]
		result = 0
		for i in range(len(s)):
			if s[i] == '(':
				stack.append(i)
			elif len(stack) == 1:
				stack[0] = i
			else:
				stack.pop()
				result = max(result, i - stack[-1])
		return result


class Solution:

	def maxLength(self, s):
		stack = [-1]
		count = 0
		for i in range(len(s)):
			if s[i] == '(':
				stack.append(i)
			elif stack and stack[-1] != -1 and (s[stack[-1]] == '('):
				stack.pop()
				count = max(count, i - stack[-1])
			else:
				stack.append(i)
		return count


class Solution:

	def maxLength(self, S):
		(stack, ans) = ([-1], 0)
		n = len(S)
		j = 1
		for i in range(n):
			if S[i] == '(':
				stack.append(i)
				j += 1
			else:
				stack.pop()
				j -= 1
				if j == 0:
					stack.append(i)
					j += 1
				else:
					ans = max(ans, i - stack[-1])
		return ans


from collections import deque

class Solution:

	def maxLength(self, S):
		maxLen = 0
		stack = deque()
		stack.append(-1)
		for i in range(len(S)):
			if S[i] == '(':
				stack.append(i)
			else:
				if stack:
					stack.pop()
				if stack:
					maxLen = max(maxLen, i - stack[len(stack) - 1])
				else:
					stack.append(i)
		return maxLen


class Solution:

	def maxLength(self, S):
		ans = 0
		dl = 0
		dr = 0
		for i in S:
			if i == ')':
				dr += 1
			else:
				dl += 1
			if dr > dl:
				dl = 0
				dr = 0
			elif dl == dr:
				ans = max(ans, dr * 2)
		dr = 0
		dl = 0
		for i in S[::-1]:
			if i == ')':
				dr += 1
			else:
				dl += 1
			if dr < dl:
				dl = 0
				dr = 0
			elif dl == dr:
				ans = max(ans, dr * 2)
		return ans


class Solution:

	def maxLength(self, S):
		stack = []
		for (i, c) in enumerate(S):
			if c == ')' and stack and (S[stack[-1]] == '('):
				stack.pop()
			else:
				stack.append(i)
		stack.append(len(S))
		max_length = stack[0]
		for index in range(1, len(stack)):
			max_length = max(max_length, stack[index] - stack[index - 1] - 1)
		return max_length


class Solution:

	def maxLength(self, s):
		l_count = r_count = max_len = 0
		i = 0
		while i < len(s):
			if s[i] == '(':
				l_count += 1
			else:
				r_count += 1
			if l_count == r_count:
				max_len = max(max_len, l_count + r_count)
			elif r_count > l_count:
				l_count = r_count = 0
			i += 1
		l_count = r_count = 0
		i = len(s) - 1
		while i >= 0:
			if s[i] == '(':
				l_count += 1
			else:
				r_count += 1
			if l_count == r_count:
				max_len = max(max_len, l_count + r_count)
			elif l_count > r_count:
				l_count = r_count = 0
			i -= 1
		return max_len


class Solution:

	def maxLength(self, S):
		(op, clo) = (0, 0)
		ans = 0
		n = len(S)
		for i in S:
			if i == '(':
				op += 1
			else:
				clo += 1
			if op == clo:
				ans = max(ans, op + clo)
			if clo > op:
				clo = 0
				op = 0
		(op, clo) = (0, 0)
		for i in range(n - 1, -1, -1):
			if S[i] == ')':
				clo += 1
			else:
				op += 1
			if op == clo:
				ans = max(ans, op + clo)
			if op > clo:
				clo = 0
				op = 0
		return ans


class Solution:

	def maxLength(self, S):
		(left, right, maxi) = (0, 0, 0)
		for i in range(len(S)):
			if S[i] == '(':
				left += 1
			else:
				right += 1
			if left == right:
				maxi = max(maxi, 2 * left)
			elif left < right:
				(left, right) = (0, 0)
		(left, right) = (0, 0)
		for i in range(len(S) - 1, -1, -1):
			if S[i] == ')':
				left += 1
			else:
				right += 1
			if left == right:
				maxi = max(maxi, 2 * left)
			elif left < right:
				(left, right) = (0, 0)
		return maxi


class Solution:

	def maxLength(self, S):
		open_par = 0
		close_par = 0
		result = 0
		for ele in S:
			if ele == '(':
				open_par += 1
			else:
				close_par += 1
			if open_par == close_par:
				result = max(result, open_par + close_par)
			elif close_par > open_par:
				open_par = 0
				close_par = 0
		open_par = 0
		close_par = 0
		for ele in range(len(S) - 1, -1, -1):
			if S[ele] == '(':
				open_par += 1
			else:
				close_par += 1
			if open_par == close_par:
				result = max(result, open_par + close_par)
			elif close_par < open_par:
				open_par = 0
				close_par = 0
		return result


class Solution:

	def maxLength(self, S):
		c = []
		ind = [-1]
		l = 0
		for i in range(len(S)):
			if S[i] == '(':
				c.append('(')
				ind.append(i)
			elif c:
				if c[-1] == '(':
					c.pop()
					ind.pop()
					l = max(l, i - ind[-1])
				else:
					c.append(')')
					ind.append(i)
			else:
				c.append(')')
				ind.append(i)
		return l


class Solution:

	def maxLength(self, S):
		left = 0
		right = 0
		res = 0
		for i in S:
			if i == '(':
				left += 1
			else:
				right += 1
			if left == right:
				res = max(res, left + right)
			elif right > left:
				left = right = 0
		left = right = 0
		for i in S[::-1]:
			if i == '(':
				left += 1
			else:
				right += 1
			if left == right:
				res = max(res, left + right)
			elif left > right:
				left = right = 0
		return res


class Solution:

	def maxLength(self, S):
		s = [-1]
		l = 0
		for i in range(len(S)):
			if S[i] == '(':
				s.append(i)
			else:
				if s:
					s.pop()
				if not s:
					s.append(i)
				else:
					l = max(l, i - s[-1])
		return l


class Solution:

	def maxLength(self, S):
		l = len(S)
		pairs = [-1 for _ in range(l)]
		stk = []
		for (i, p) in enumerate(S):
			if p == '(':
				stk.append((p, i))
			elif len(stk):
				pairs[i] = stk[-1][1]
				pairs[stk[-1][1]] = i
				stk.pop()
		s = 0
		i = 0
		max_len = 0
		while i < l:
			if pairs[i] == -1:
				i += 1
				s = i
				continue
			i += 1
			max_len = max(max_len, i - s)
		return max_len


class Solution:

	def maxLength(self, S):
		l = [-1]
		l1 = 0
		for (i, p) in enumerate(S):
			if p == '(':
				l.append(i)
			else:
				l.pop()
				if not l:
					l.append(i)
				else:
					l1 = max(l1, i - l[-1])
		return l1


class Solution:

	def maxLength(self, S):
		lst = [-1]
		lv = 0
		for (i, p) in enumerate(S):
			if p == '(':
				lst.append(i)
			else:
				lst.pop()
				if not lst:
					lst.append(i)
				else:
					lv = max(lv, i - lst[-1])
		return lv


class Solution:

	def maxLength(self, S):
		flag = False
		res = 0
		stack = []
		balance = 0
		for i in range(len(S)):
			if S[i] == '(':
				balance += 1
				if not flag:
					idx = i
					flag = True
			else:
				balance -= 1
			if stack and S[i] == ')':
				stack.pop(-1)
			if stack:
				if S[i] == ')':
					res = max(res, i - stack[-1])
			elif balance == 0:
				res = max(res, i + 1 - idx)
			elif balance < 0:
				flag = False
				balance = 0
			if S[i] == '(':
				stack.append(i)
		return res


class Solution:

	def maxLength(self, S):
		stk = []
		i = 0
		while i < len(S):
			if S[i] == '(':
				stk.append('(')
			elif len(stk) == 0:
				stk.append(')')
			elif stk[-1] == '(':
				stk.pop()
				stk.append('2')
			else:
				c = '0'
				while len(stk) > 0 and stk[-1].isdigit():
					c = str(int(c) + int(stk.pop()))
				if len(stk) == 0:
					stk.append(c)
					stk.append(')')
				elif stk[-1] == '(':
					stk.pop()
					stk.append(str(int(c) + 2))
				else:
					stk.append(c)
					stk.append(')')
			i += 1
		ans = 0
		x = 0
		while len(stk) > 0:
			if stk[-1].isdigit():
				x += int(stk.pop())
			else:
				ans = max(ans, x)
				x = 0
				stk.pop()
		ans = max(ans, x)
		return ans


class Solution:

	def maxLength(self, S):
		mx = 0
		st = [-1]
		for (i, j) in enumerate(S):
			if j == '(':
				st.append(i)
			else:
				st.pop()
				if not st:
					st.append(i)
				else:
					mx = max(mx, i - st[-1])
		return mx


from collections import deque

class Solution:

	def maxLength(self, s):
		stack = deque()
		anslength = 0
		stack.append(-1)
		if not s:
			return anslength
		for i in range(len(s)):
			if s[i] == '(':
				stack.append(i)
			else:
				stack.pop()
				if not stack:
					stack.append(i)
				else:
					length = i - stack[-1]
					anslength = max(anslength, length)
		return anslength


class Solution:

	def maxLength(self, S):
		if len(S) == 0:
			return 0
		stk = []
		ans = 0
		final_ans = 0
		for i in range(len(S)):
			ss = S[i]
			if len(stk) <= 0:
				stk.append([S[i], i])
			elif stk[-1][0] == '(' and S[i] == ')':
				stk.pop(-1)
			elif stk[-1][0] == '(' and S[i] == '(':
				stk.append([S[i], i])
			else:
				stk.append([S[i], i])
		prev = None
		stk.insert(0, ['', -1])
		stk.append(['', len(S)])
		for i in range(len(stk) - 1, 0, -1):
			final_ans = max(final_ans, stk[i][1] - stk[i - 1][1] - 1)
		return final_ans


class Solution1(object):

	def maxLength(self, S):
		(stack, maxLen) = ([], 0)
		stack.append(-1)
		for index in range(len(S)):
			if S[index] == '(':
				stack.append(index)
			else:
				if stack:
					stack.pop()
				if stack:
					maxLen = max(maxLen, index - stack[-1])
				else:
					stack.append(index)
		return maxLen

class Solution(object):

	def maxLength(self, S):
		maxLen = 0
		left = right = 0
		for index in range(len(S)):
			if S[index] == '(':
				left += 1
			else:
				right += 1
			if left == right:
				maxLen = max(maxLen, 2 * right)
			if right > left:
				left = right = 0
		left = right = 0
		for index in range(len(S) - 1, -1, -1):
			if S[index] == '(':
				left += 1
			else:
				right += 1
			if left == right:
				maxLen = max(maxLen, 2 * right)
			if left > right:
				left = right = 0
		return maxLen


class Solution(object):

	def maxLength(self, S):
		(stack, maxLen) = ([], 0)
		stack.append(-1)
		for index in range(len(S)):
			if S[index] == '(':
				stack.append(index)
			else:
				if stack:
					stack.pop()
				if stack:
					maxLen = max(maxLen, index - stack[-1])
				else:
					stack.append(index)
		return maxLen


class Solution:

	def is_valid(self, S):
		stack = []
		for i in S:
			if i == '(':
				stack.append(i)
			else:
				if not stack:
					return False
				ch = stack.pop(-1)
		if len(stack):
			return False
		return True

	def maxLength(self, S):
		n = len(S)
		stack = [-1]
		max_length = 0
		for i in range(n):
			if S[i] == '(':
				stack.append(i)
			else:
				stack.pop()
				if not len(stack):
					stack.append(i)
				else:
					sum_ = i - stack[-1]
					if sum_ > max_length:
						max_length = sum_
		return max_length


class Solution:

	def maxLength(self, S):
		n = len(S)
		dp = [0] * n
		m = 0
		for i in range(1, n):
			if S[i] == ')' and i - dp[i - 1] - 1 >= 0 and (S[i - dp[i - 1] - 1] == '('):
				dp[i] = dp[i - 1] + 2
				if i - dp[i - 1] - 2 >= 0:
					dp[i] += dp[i - dp[i - 1] - 2]
				m = max(m, dp[i])
		return m


class Solution:

	def maxLength(self, S):
		n = len(S)
		stk = [-1]
		result = 0
		for i in range(n):
			if S[i] == '(':
				stk.append(i)
			else:
				size = len(stk)
				if size != 0:
					stk.pop()
					size -= 1
				if size != 0:
					if result < i - stk[size - 1]:
						result = i - stk[size - 1]
				else:
					stk.append(i)
		return result


class Solution:

	def maxLength(self, S):
		maxx = 0
		q = []
		q.append(-1)
		for i in range(len(S)):
			if '(' == S[i]:
				q.append(i)
			else:
				q.pop()
				if not q:
					q.append(i)
				else:
					k = i - q[-1]
					maxx = max(maxx, k)
		return maxx


class Solution:

	def maxLength(self, S):
		ans = o = c = 0
		for i in S:
			if i == '(':
				o += 1
			else:
				c += 1
			if o == c:
				ans = max(ans, 2 * o)
			elif c > o:
				o = c = 0
		o = c = 0
		for j in range(len(S) - 1, -1, -1):
			if S[j] == '(':
				o += 1
			else:
				c += 1
			if o == c:
				ans = max(ans, 2 * o)
			elif o > c:
				o = c = 0
		return ans


class Solution:

	def maxLength(self, S):
		stack = []
		stack.append(-1)
		maxl = 0
		i = 0
		while i < len(S):
			if S[i] == '(':
				stack.append(i)
			else:
				stack.pop()
				if len(stack) == 0:
					stack.append(i)
				else:
					maxl = max(maxl, i - stack[-1])
			i = i + 1
		return maxl