Given a string S consisting only of opening and closing parenthesis 'ie '('  and ')', find out the length of the longest valid(well-formed) parentheses substring.
NOTE: Length of the smallest valid substring ( ) is 2.
Example 1:
Input: S = "(()("
Output: 2
Explanation: The longest valid 
substring is "()". Length = 2.
Example 2:
Input: S = "()(())("
Output: 6
Explanation: The longest valid 
substring is "()(())". Length = 6.
Your Task:  
You dont need to read input or print anything. Complete the function findMaxLen() which takes S as input parameter and returns the maxlength.
Expected Time Complexity:O(n)
Expected Auxiliary Space: O(1)   
Constraints:
1 <= |S| <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def findMaxLen(ob, S):
        # code here 

Solutions:
class Solution:

	def findMaxLen(ob, s):
		(open, close, ans) = (0, 0, 0)
		for i in s:
			if i == '(':
				open += 1
			else:
				close += 1
			if close == open:
				ans = max(ans, close + open)
			elif close > open:
				open = close = 0
		open = close = 0
		for i in range(len(s) - 1, -1, -1):
			if '(' == s[i]:
				open += 1
			else:
				close += 1
			if close == open:
				ans = max(ans, close + open)
			elif open > close:
				open = close = 0
		return ans


class Solution:

	def findMaxLen(ob, s):
		stack = []
		stack.append(-1)
		ans = 0
		for i in range(len(S)):
			if S[i] == '(':
				stack.append(i)
			else:
				stack.pop()
				if len(stack) == 0:
					stack.append(i)
				ans = max(ans, i - stack[-1])
		return ans


class Solution:

	def findMaxLen(ob, S):
		st = []
		result = 0
		st.append(-1)
		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 findMaxLen(self, s):
		st = [-1]
		maxi = 0
		for i in range(0, len(s)):
			brac = s[i]
			if brac == '(':
				st.append(i)
			else:
				st.pop()
				if len(st) == 0:
					st.append(i)
				else:
					maxi = max(maxi, i - st[-1])
		return maxi


class Solution:

	def findMaxLen(ob, S):
		if S == None or len(S) < 2:
			return 0
		st = []
		for i in range(len(S)):
			if S[i] == '(':
				st.append(i)
			elif len(st) != 0 and S[st[-1]] == '(':
				st.pop()
			else:
				st.append(i)
		maxel = 0
		end = len(S)
		while len(st) != 0:
			element = st.pop()
			maxel = max(maxel, end - element - 1)
			end = element
		return max(end, maxel)


class Solution:

	def findMaxLen(ob, S):
		opened = 0
		closed = 0
		n = len(S)
		Len1 = 0
		for i in range(n):
			if S[i] == '(':
				opened += 1
			else:
				closed += 1
			if opened == closed:
				Len1 = max(Len1, opened + closed)
			elif closed > opened:
				opened = 0
				closed = 0
		opened = 0
		closed = 0
		for i in range(n - 1, 0, -1):
			if S[i] == '(':
				opened += 1
			else:
				closed += 1
			if opened == closed:
				Len1 = max(Len1, opened + closed)
			elif opened > closed:
				opened = 0
				closed = 0
		return Len1


class Solution:

	def findMaxLen(ob, S):
		stack = [-1]
		max_len = 0
		for i in range(len(S)):
			if S[i] == '(':
				stack.append(i)
			else:
				stack.pop()
				if len(stack) == 0:
					stack.append(i)
				else:
					curr_length = i - stack[-1]
					max_len = max(curr_length, max_len)
		return max_len


class Solution:

	def findMaxLen(ob, 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 findMaxLen(ob, S):
		stack = []
		n = len(S)
		stack.append(0)
		for i in range(n):
			if len(stack) > 1 and (S[i] == ')' and S[stack[-1] - 1] == '('):
				stack.pop()
			else:
				stack.append(i + 1)
		stack.append(n + 1)
		m = 0
		for i in range(len(stack) - 1):
			m = max(m, stack[i + 1] - stack[i] - 1)
		return m


class Solution:

	def findMaxLen(ob, S):
		a = 0
		b = []
		for x in range(len(S)):
			if S[x] == '(':
				b.append(x)
				a += 1
			elif a > 0:
				a -= 1
				b.pop(-1)
			else:
				b.append(x)
		diff = 0
		for x in range(1, len(b)):
			if b[x] - b[x - 1] - 1 > diff:
				diff = b[x] - b[x - 1] - 1
		if not b:
			return len(S)
		if b[0] != 0:
			if b[0] > diff:
				diff = b[0]
		if b[-1] != len(S) - 1:
			if len(S) - 1 - b[-1] > diff:
				diff = len(S) - 1 - b[-1]
		return diff


class Solution:

	def findMaxLen(ob, S):
		a = 0
		b = []
		d = 0
		c = []
		previous = 0
		for x in range(len(S)):
			if S[x] == '(':
				a += 1
				b.append(x)
			elif a > 0:
				a -= 1
				b.pop(-1)
				d += 1
			else:
				c.append(x)
		b[:] = b + c
		b.sort()
		diff = 0
		for x in range(1, len(b)):
			if b[x] - b[x - 1] - 1 > diff:
				diff = b[x] - b[x - 1] - 1
		if b:
			if b[0] != 0:
				if b[0] > diff:
					diff = b[0]
			if b[-1] != len(S) - 1:
				if len(S) - 1 - b[-1] > diff:
					diff = len(S) - 1 - b[-1]
		else:
			return len(S)
		return diff


from collections import deque

class Solution:

	def findMaxLen(ob, S):
		res = 0
		stack = deque()
		stack.append(-1)
		for i in range(len(S)):
			if S[i] == '(':
				stack.append(i)
			else:
				if len(stack) != 0:
					stack.pop()
				if len(stack) != 0:
					res = max(res, i - stack[-1])
				else:
					stack.append(i)
		return res


class Solution:

	def findMaxLen(ob, S):
		st = []
		n = len(S)
		for i in range(n):
			if S[i] == '(':
				st.append(i)
			elif len(st) != 0 and S[st[-1]] == '(':
				st.pop()
			else:
				st.append(i)
		maxi = 0
		l = len(S)
		while len(st) != 0:
			le = st.pop()
			maxi = max(maxi, l - le - 1)
			l = le
		return max(l, maxi)


def max_valid_sub_string_length(input_str: str):
	n = len(input_str)
	data_stack = [-1]
	answer = 0
	for i in range(n):
		if input_str[i] == '(':
			data_stack.append(i)
		else:
			data_stack.pop(-1)
			if len(data_stack) > 0:
				diff = i - data_stack[-1]
				answer = max(answer, diff)
			if len(data_stack) == 0:
				data_stack.append(i)
	return answer

class Solution:

	def findMaxLen(ob, S):
		return max_valid_sub_string_length(S)


class Solution:

	def findMaxLen(ob, S):
		stack = [-1]
		res = 0
		for (i, c) in enumerate(S):
			if c == '(':
				stack.append(i)
			else:
				stack.pop()
			if len(stack) == 0:
				stack.append(i)
			else:
				res = max(res, i - stack[-1])
		return res


class Solution:

	def findMaxLen(self, s):
		st = []
		for i in range(len(s)):
			if s[i] == '(':
				st.append(i)
			elif st and s[i] == ')' and (s[st[-1]] != '('):
				st.append(i)
			elif st and s[i] == ')' and (s[st[-1]] == '('):
				st.pop()
			else:
				st.append(i)
		n = len(s)
		max_ans = 0
		if st and st[-1] != 0:
			max_ans = max(max_ans, st[0] - 0)
		for i in range(1, len(st)):
			max_ans = max(max_ans, st[i] - st[i - 1] - 1)
		if st and st[-1] < n:
			max_ans = max(max_ans, n - st[-1] - 1)
		if not st and len(s) > 0:
			return len(s)
		return max_ans


class Solution:

	def findMaxLen(ob, S):
		stack = [-1]
		max1 = 0
		for i in range(len(S)):
			if S[i] == '(':
				stack.append(i)
			elif len(stack) > 1:
				stack.pop()
				max1 = max(max1, i - stack[-1])
			else:
				stack[0] = i
		return max1


class Solution:

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


class Solution:

	def findMaxLen(ob, s):
		left = 0
		right = 0
		maxLength = 0
		for i in range(0, len(s)):
			if s[i] == '(':
				left += 1
			else:
				right += 1
			if right > left:
				left = 0
				right = 0
			elif right == left:
				maxLength = max(maxLength, 2 * right)
		left = 0
		right = 0
		for i in range(len(s) - 1, -1, -1):
			if s[i] == ')':
				left += 1
			else:
				right += 1
			if right > left:
				left = 0
				right = 0
			elif right == left:
				maxLength = max(maxLength, 2 * right)
		return maxLength


class Solution:

	def findMaxLen(ob, S):
		maxi = 0
		stack = [-1]
		for i in range(len(S)):
			if S[i] == '(':
				stack.append(i)
			else:
				stack.pop()
				if not stack:
					stack.append(i)
				else:
					maxi = max(maxi, i - stack[-1])
		return maxi


class Solution:

	def findMaxLen(ob, s):
		stack = [-1]
		max_len = 0
		for i in range(len(s)):
			if s[i] == '(':
				stack.append(i)
			else:
				stack.pop()
				if not stack:
					stack.append(i)
				else:
					max_len = max(max_len, i - stack[-1])
		return max_len


class Solution:

	def findMaxLen(ob, s):
		(l, r) = (0, 0)
		mx = 0
		for i in s:
			if i == '(':
				l += 1
			else:
				r += 1
			if l == r:
				mx = max(mx, r * 2)
			elif r > l:
				(l, r) = (0, 0)
		(l, r) = (0, 0)
		for i in reversed(s):
			if i == ')':
				r += 1
			else:
				l += 1
			if l == r:
				mx = max(mx, r * 2)
			elif l > r:
				(l, r) = (0, 0)
		return mx


class Solution:

	def findMaxLen(ob, 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 findMaxLen(ob, S):
		(l, r) = (0, 0)
		ans = 0
		for i in range(len(S)):
			if S[i] == '(':
				l = l + 1
			else:
				r = r + 1
			if l == r:
				ans = max(ans, 2 * l)
			elif r > l:
				r = l = 0
		(l, r) = (0, 0)
		for i in range(len(S) - 1, 0, -1):
			if S[i] == '(':
				l = l + 1
			else:
				r = r + 1
			if l == r:
				ans = max(ans, 2 * l)
			elif l > r:
				r = l = 0
		return ans


class Solution:

	def findMaxLen(ob, 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 findMaxLen(ob, S):
		stk = []
		stk.append(-1)
		maxlen = 0
		for i in range(len(S)):
			if S[i] == '(':
				stk.append(i)
			else:
				x = stk.pop(-1)
				if len(stk) != 0:
					maxlen = max(maxlen, i - stk[-1])
				else:
					stk.append(i)
		return maxlen


class Solution:

	def findMaxLen(ob, 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 findMaxLen(ob, s):
		char_stack = []
		ind_stack = [-1]
		ans = 0
		for i in range(len(s)):
			c = s[i]
			if c == '(':
				char_stack.append(c)
				ind_stack.append(i)
			elif c == ')':
				if char_stack and char_stack[-1] == '(':
					char_stack.pop()
					ind_stack.pop()
					ans = max(ans, i - ind_stack[-1])
				else:
					char_stack.append(c)
					ind_stack.append(i)
		return ans


class Solution:

	def findMaxLen(ob, 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 findMaxLen(ob, S):
		stack = []
		mxl = 0
		(l, r) = (0, 0)
		n = len(S)
		for i in range(n):
			if S[i] == '(':
				l += 1
			else:
				r += 1
			if l == r:
				mxl = max(mxl, 2 * r)
			elif l < r:
				(l, r) = (0, 0)
		(l, r) = (0, 0)
		for i in range(n - 1, 0, -1):
			if S[i] == '(':
				l += 1
			else:
				r += 1
			if l == r:
				mxl = max(mxl, 2 * r)
			elif l > r:
				(l, r) = (0, 0)
		return mxl


class Solution:

	def findMaxLen(ob, S):
		n = len(S)
		st = []
		for i in range(len(S)):
			if S[i] == '(':
				st.append(i)
			elif len(st) != 0 and S[st[-1]] == '(':
				st.pop()
			else:
				st.append(i)
		mx = 0
		end = len(S)
		while len(st) > 0:
			ele = st[-1]
			st.pop()
			mx = max(mx, end - ele - 1)
			end = ele
		return max(end, mx)


class Solution:

	def findMaxLen(ob, S):
		s = [-1]
		max_length = 0
		for i in range(len(S)):
			if S[i] == '(':
				s.append(i)
			elif len(s) > 1:
				s.pop()
				max_length = max(max_length, i - s[-1])
			else:
				s[0] = i
		return max_length


class Solution:

	def findMaxLen(ob, 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 findMaxLen(ob, S):
		stack = [-1]
		maxLen = 0
		for index in range(len(S)):
			curr = S[index]
			if curr == '(':
				stack.append(index)
			else:
				stack.pop()
				if not stack:
					stack.append(index)
				else:
					maxLen = max(maxLen, index - stack[-1])
		return maxLen


class Solution:

	def findMaxLen(ob, 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 Solution:

	def findMaxLen(ob, 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


class Solution:

	def findMaxLen(ob, s):
		s1 = [-1]
		res = 0
		for i in range(len(s)):
			if s[i] == '(':
				s1.append(i)
			else:
				if len(s1) != 0:
					s1.pop()
				if len(s1) != 0:
					res = max(res, i - s1[len(s1) - 1])
				else:
					s1.append(i)
		return res


class Solution:

	def findMaxLen(ob, S):
		s1 = []
		c = 0
		s1.append(-1)
		for i in range(0, len(S)):
			if S[i] == '(':
				s1.append(i)
			else:
				s1.pop()
			if len(s1) == 0:
				s1.append(i)
			else:
				c = max(c, i - s1[-1])
		return c


class Solution:

	def findMaxLen(ob, S):
		(res, cnt) = (0, 0)
		stack = []
		arr = [0] * len(S)
		for i in range(0, len(S)):
			if S[i] == '(':
				stack.append(i)
			elif len(stack):
				arr[stack.pop()] = 1
				arr[i] = 1
		for i in range(len(S)):
			if arr[i]:
				cnt += 1
			else:
				cnt = 0
			res = max(res, cnt)
		return res


class Solution:

	def findMaxLen(ob, s):
		l = []
		m = 0
		count = 0
		for i in s:
			if len(l) == 0:
				l.append(i)
				continue
			if len(l) > 0 and l[len(l) - 1] != ')' and (l[len(l) - 1] != '('):
				while len(l) > 0 and l[len(l) - 1] != '(' or l[len(l) - 1] != ')':
					x = l.pop()
					if len(l) > 0 and l[len(l) - 1] != '(' and (l[len(l) - 1] != ')'):
						l[len(l) - 1] = l[len(l) - 1] + x
						break
					l.append(x)
					break
			if i == ')':
				if len(l) == 0:
					count = 0
					l.append(i)
					continue
				if l[len(l) - 1] == ')':
					count = 0
					l.append(i)
					continue
				if l[len(l) - 1] == '(':
					l.pop()
					count = count + 2
					l.append(count)
					count = 0
					continue
				if l[len(l) - 1] != '(' and l[len(l) - 1] != ')':
					x = l.pop()
					if len(l) > 0 and l[len(l) - 1] == '(':
						x = x + 2
						l.pop()
						l.append(x)
						continue
					l.append(x)
					l.append(i)
			if i == '(':
				l.append(i)
		count = 0
		for i in l:
			if i != ')' and i != '(':
				count = count + i
				m = max(m, count)
				continue
			count = 0
		return m


class Solution:

	def findMaxLen(ob, s):
		st = [-1]
		c = 0
		op = []
		maxc = 0
		for i in range(len(s)):
			if s[i] == '(':
				st.append(i)
				op.append(s[i])
			elif len(op) == 0 and s[i] == ')':
				st.append(i)
			else:
				op.pop()
				st.pop()
				c = i - st[-1]
			maxc = max(maxc, c)
		return maxc


class Solution:

	def findMaxLen(ob, S):
		n = len(S)
		mvs = 0
		left = 0
		right = 0
		for i in range(n):
			if S[i] == '(':
				left += 1
			else:
				right += 1
			if left == right:
				mvs = max(mvs, 2 * right)
			elif right > left:
				left = right = 0
		left = right = 0
		for i in reversed(range(n)):
			if S[i] == '(':
				left += 1
			else:
				right += 1
			if left == right:
				mvs = max(mvs, 2 * left)
			elif left > right:
				left = right = 0
		return mvs


class Solution:

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


class Solution:

	def findMaxLen(ob, s):
		left = 0
		right = 0
		cnt = 0
		for i in s:
			if i == '(':
				left += 1
			else:
				right += 1
			if left == right:
				cnt = max(cnt, 2 * right)
			elif right > left:
				left = 0
				right = 0
		left = 0
		right = 0
		for i in s[::-1]:
			if i == ')':
				left += 1
			else:
				right += 1
			if left == right:
				cnt = max(cnt, 2 * left)
			elif right > left:
				left = 0
				right = 0
		return cnt


class Solution:

	def findMaxLen(ob, s):
		l1 = []
		cnt = 0
		n = len(s)
		l1.append(-1)
		for i in range(n):
			if s[i] == '(':
				l1.append(i)
			else:
				if len(l1) != 0:
					l1.pop()
				if len(l1) != 0:
					cnt = max(cnt, i - l1[-1])
				else:
					l1.append(i)
		return cnt


class Solution:

	def findMaxLen(ob, S):
		stack = [-1]
		max_len = 0
		for (i, c) in enumerate(S):
			if c == '(':
				stack.append(i)
			elif stack:
				stack.pop()
				if stack:
					max_len = max(max_len, i - stack[-1])
				else:
					stack.append(i)
		return max_len