Given a string s of '(' , ')' and lowercase English characters. 
Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.
Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

 
Example 1:
Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Example 2:
Input: s = "a)b(c)d"
Output: "ab(c)d"

Example 3:
Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.

Example 4:
Input: s = "(a(b(c)d)"
Output: "a(b(c)d)"

 
Constraints:

1 <= s.length <= 10^5
s[i] is one of  '(' , ')' and lowercase English letters.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        

Solutions:
class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		if not s:
			return s
		l = 0
		r = 0
		res = ''
		for (i, c) in enumerate(s):
			if c == '(':
				l += 1
			if c == ')':
				if l == r:
					continue
				else:
					r += 1
			res += c
		s = res
		l = 0
		r = 0
		res = ''
		for i in range(len(s) - 1, -1, -1):
			c = s[i]
			if c == ')':
				r += 1
			if c == '(':
				if l == r:
					continue
				else:
					l += 1
			res = c + res
		return res


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		stack = []
		to_remove = set()
		for (i, c) in enumerate(s):
			if c == '(':
				stack.append(i)
			elif c == ')':
				if stack:
					stack.pop()
				else:
					to_remove.add(i)
		print(to_remove)
		to_remove |= set(stack)
		print(to_remove)
		return ''.join((c for (i, c) in enumerate(s) if i not in to_remove))


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		total = 0
		new_s = ''
		recent_opens = []
		for char in s:
			if char == '(':
				total += 1
				new_s = ''.join((new_s, char))
				recent_opens.append(len(new_s) - 1)
			elif char == ')':
				total -= 1
				if total >= 0:
					new_s = ''.join((new_s, char))
					recent_opens.pop()
				else:
					total = 0
			else:
				new_s = ''.join((new_s, char))
		if total > 0:
			for (count, index) in enumerate(recent_opens):
				total -= 1
				new_s = ''.join((new_s[:index - count], new_s[index - count + 1:]))
				if total <= 0:
					break
		return new_s


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		open_bracket = set()
		redundant_indices = set()
		for i in range(len(s)):
			if s[i] == '(':
				open_bracket.add(i)
			elif s[i] == ')' and len(open_bracket) > 0:
				open_bracket.remove(max(open_bracket))
			elif s[i] == ')' and len(open_bracket) == 0:
				redundant_indices.add(i)
		if open_bracket:
			for bracket in open_bracket:
				redundant_indices.add(bracket)
		result = ''
		for i in range(len(s)):
			if i not in redundant_indices:
				result += s[i]
		return result


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		res = []
		stack = []
		for ele in s:
			if ele not in '()':
				res.append(ele)
			elif ele == '(':
				stack.append(ele)
				res.append(ele)
			elif ele == ')':
				if stack != [] and stack[-1] == '(':
					res.append(ele)
					stack.pop()
		if stack == []:
			return ''.join(res)
		else:
			i = len(res) - 1
			while stack:
				if res[i] == stack[-1]:
					stack.pop()
					res = res[:i] + res[i + 1:]
				i = i - 1
			return ''.join(res)


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		stack = []
		from collections import defaultdict
		data_dict = defaultdict(list)
		for index in range(0, len(s)):
			char = s[index]
			if char == '(':
				data_dict['('].append(index)
				stack.append('(')
			if char == ')':
				if '(' in stack:
					stack.pop()
					data_dict['('].pop()
				else:
					stack.append(')')
					data_dict[')'].append(index)
		s_list = list(s)
		for char in stack:
			parentheses_index_list = data_dict[char]
			remove_char_index = parentheses_index_list.pop()
			s_list.pop(remove_char_index)
			if char == '(':
				parentheses_index_list = data_dict[')']
				for index in range(0, len(parentheses_index_list)):
					position_in_s = parentheses_index_list[index]
					if position_in_s > remove_char_index:
						position_in_s -= 1
						parentheses_index_list[index] = position_in_s
			else:
				parentheses_index_list = data_dict['(']
				for index in range(0, len(parentheses_index_list)):
					position_in_s = parentheses_index_list[index]
					if position_in_s > remove_char_index:
						position_in_s -= 1
						parentheses_index_list[index] = position_in_s
		return_s = ''
		for char in s_list:
			return_s += char
		return return_s


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		(c, st, st2, res) = (0, [], [], [])
		for (j, ss) in enumerate(s):
			if ss == '(':
				st.append(j)
			elif ss == ')':
				if st:
					st.pop()
				else:
					st2.append(j)
			else:
				continue
		for (j, ss) in enumerate(s):
			if ss == '(' and j in st or (ss == ')' and j in st2):
				continue
			res.append(ss)
		return ''.join(res)


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		to_remove = set()
		stack = []
		for (i, c) in enumerate(s):
			if c == '(':
				stack.append(i)
			elif c == ')':
				if len(stack):
					stack.pop()
					continue
				to_remove.add(i)
		for i in stack:
			to_remove.add(i)
		st = ''
		for (i, c) in enumerate(s):
			if i not in to_remove:
				st += c
		return ''.join(st)


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		stack = []
		p = []
		for (index, item) in enumerate(s):
			if item == '(':
				stack.append(index)
			elif item == ')' and stack:
				p.append([stack.pop(), index])
		s = s.replace(')', '_').replace('(', '_')
		for [l, r] in p:
			s = s[:l] + '(' + s[l + 1:r] + ')' + s[r + 1:]
		return s.replace('_', '')


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		stack = []
		index_to_remove = set()
		for (index, item) in enumerate(s):
			if item == '(':
				stack.append(index)
			elif item == ')':
				if not stack:
					index_to_remove.add(index)
				else:
					stack.pop()
		print(stack)
		print(index_to_remove)
		string_builder = []
		for (index, item) in enumerate(s):
			if index not in stack and index not in index_to_remove:
				string_builder.append(item)
		return ''.join(string_builder)


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		stack = []
		updated_s = []
		for ch in s:
			if ch not in {'(', ')'}:
				updated_s.append(ch)
			elif ch == '(':
				stack.append((ch, len(updated_s)))
				updated_s.append(ch)
			elif stack:
				updated_s.append(ch)
				stack = stack[:-1]
		if stack:
			for i in stack[::-1]:
				updated_s = updated_s[:i[1]] + updated_s[i[1] + 1:]
		return ''.join(updated_s)


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		level = 0
		result = list(s)
		open_pos = []
		close_pos = []
		for (i, c) in enumerate(s):
			if c == '(':
				level += 1
				open_pos.append(i)
			elif c == ')':
				open_idx = None
				if open_pos:
					open_idx = open_pos.pop()
				if level == 0:
					if open_idx:
						result[open_idx] = '_'
					result[i] = '_'
				else:
					level -= 1
		return ''.join([x for (i, x) in enumerate(result) if x != '_' and (not i in open_pos)])


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		cnt_left = 0
		rev_left = []
		rev_right = set()
		for (i, c) in enumerate(s):
			if c == ')':
				if cnt_left == 0:
					rev_right.add(i)
				else:
					rev_left.pop()
					cnt_left -= 1
			elif c == '(':
				rev_left.append(i)
				cnt_left += 1
		rev = rev_right.union(set(rev_left))
		res = []
		for i in range(len(s)):
			if i not in rev_right and i not in rev_left:
				res.append(s[i])
		return ''.join(res)


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		cleaned = {}
		stack = []
		for (i, ch) in enumerate(s):
			if ch == ')':
				if len(stack):
					cleaned[i] = ')'
					stack.pop()
				else:
					cleaned[i] = ''
				continue
			if ch == '(':
				stack.append(i)
			cleaned[i] = ch
		output = []
		for item in cleaned.items():
			if item[0] not in stack:
				output.append(item[1])
		return ''.join(output)


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		l = list(s)
		stack = []
		i = 0
		while i < len(l):
			if l[i] == '(':
				stack.append(i)
			elif l[i] == ')':
				if stack:
					stack.pop()
				else:
					del l[i]
					i -= 1
			i += 1
		return ''.join([c for (i, c) in enumerate(l) if i not in stack])


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		stackparen = []
		stackindex = []
		result = ''
		result1 = ''
		i = 0
		j = 0
		while i <= len(s) - 1:
			if s[i] == ')' and len(stackparen) == 0:
				i += 1
				continue
			if s[i] == '(':
				stackparen.append(s[i])
				stackindex.append(j)
			if s[i] == ')' and len(stackparen) > 0:
				stackparen.pop()
				stackindex.pop()
			result += s[i]
			j += 1
			i += 1
		for (j, i) in enumerate(result):
			if j not in stackindex:
				result1 += result[j]
		return result1


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		p_stack = []
		new_string = ''

		def add_char(s: str, new: str) -> str:
			added = s + new
			return added

		def tmp_change(s: str, chg: int) -> str:
			new = s[:chg] + '0' + s[chg + 1:]
			return new

		def end_change(s: str) -> str:
			new = ''
			for i in range(0, len(s)):
				if s[i] != '0':
					new = add_char(new, s[i])
			return new
		for i in range(0, len(s)):
			if s[i] == '(':
				p_stack.append(i)
				new_string = add_char(new_string, s[i])
			elif s[i] == ')':
				if len(p_stack) > 0:
					p_stack.pop()
					new_string = add_char(new_string, s[i])
				else:
					new_string = add_char(new_string, '0')
			else:
				new_string = add_char(new_string, s[i])
		if p_stack != []:
			for i in p_stack:
				new_string = tmp_change(new_string, i)
			print(new_string)
		no_zeroes = end_change(new_string)
		print(no_zeroes)
		return no_zeroes


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		pt = {'(': [], ')': []}
		for i in range(len(s)):
			if s[i].isalpha() and s[i].islower():
				continue
			elif s[i] == '(':
				pt['('].append(i)
			elif s[i] == ')':
				pt[')'].append(i)
		to_remove = []
		while pt['('] and pt[')']:
			if pt['('][0] < pt[')'][0]:
				del pt['('][0]
				del pt[')'][0]
			else:
				to_remove.append(pt[')'][0])
				del pt[')'][0]
		if pt['(']:
			to_remove.extend(pt['('])
		if pt[')']:
			to_remove.extend(pt[')'])
		res = ''
		prev = 0
		for i in to_remove:
			res += s[prev:i]
			prev = i + 1
		res += s[prev:]
		return res


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		(left, right) = (0, 0)
		result = []
		for (i, c) in enumerate(s):
			if c == '(':
				left += 1
				result.append(c)
			elif c == ')':
				if right + 1 > left:
					continue
				else:
					right += 1
					result.append(c)
			else:
				result.append(c)
		while left > right:
			i = len(result) - result[::-1].index('(') - 1
			result = result[:i] + result[i + 1:]
			left -= 1
		return ''.join(result)


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		parens = []
		to_remove = set()
		for i in range(len(s)):
			c = s[i]
			if c == ')':
				if not parens:
					to_remove.add(i)
				else:
					parens.pop()
			elif c == '(':
				parens.append(i)
		string = ''
		for i in range(len(s)):
			if i in to_remove or i in parens:
				continue
			else:
				string += s[i]
		return string


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		stack = []
		out = []
		left_pos = []
		l = 0
		for c in s:
			if c != '(' and c != ')':
				out.append(c)
				l += 1
			elif c == '(':
				out.append(c)
				stack.append(c)
				left_pos.append(l)
				l += 1
			elif stack:
				out.append(c)
				stack = stack[:-1]
				left_pos = left_pos[:-1]
				l += 1
		out_string = ''
		for i in range(len(out)):
			if i not in left_pos:
				out_string += out[i]
		return out_string


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		stacklp = []
		stackrp = []
		for i in range(len(s)):
			if s[i] == '(':
				stacklp.append(i)
			elif s[i] == ')':
				if stacklp != []:
					stacklp.pop()
				else:
					stackrp.append(i)
		stack = sorted(stacklp + stackrp)
		res = ''
		for i in range(len(s)):
			if i not in stack:
				res = res + s[i]
		return res


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		if len(s) == 0:
			return s
		stack = []
		out_s = ''
		i = 0
		for c in s:
			if c == ')':
				if len(stack) > 0:
					stack.pop()
					out_s += c
					i += 1
			elif c == '(':
				stack.append(i)
				out_s += c
				i += 1
			else:
				out_s += c
				i += 1
		if len(stack) > 0:
			out_s = [out_s[i] for i in range(len(out_s)) if i not in stack]
		return out_s


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		stack = []
		skip = []
		for (i, c) in enumerate(s):
			if c in '()':
				if c == '(':
					stack.append(i)
				elif stack:
					stack.pop()
				else:
					skip.append(i)
		while stack:
			skip.append(stack.pop())
		t = []
		for (i, c) in enumerate(s):
			if i not in skip:
				t.append(c)
		return ''.join(t)


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		cnt_left = 0
		(rev_left, rev_right) = ([], [])
		for (i, c) in enumerate(s):
			if c == ')':
				if cnt_left == 0:
					rev_right.append(i)
				else:
					rev_left.pop()
					cnt_left -= 1
			elif c == '(':
				rev_left.append(i)
				cnt_left += 1
		res = ''
		for i in range(len(s)):
			if i not in rev_right and i not in rev_left:
				res += s[i]
		return res


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		(stack, index, res) = ([], [], '')
		for i in range(len(s)):
			if s[i] == '(':
				stack.append((i, s[i]))
			elif s[i] == ')':
				if not stack:
					index.append(i)
				elif stack[-1][1] == '(':
					stack.pop()
		while stack:
			index.append(stack.pop()[0])
		for i in range(len(s)):
			if i not in index:
				res += s[i]
		return res


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		open_q = list()
		drop = list()
		for idx in range(len(s)):
			if s[idx] not in ['(', ')']:
				continue
			if s[idx] == '(':
				open_q.append(idx)
			elif open_q:
				open_q.pop()
			else:
				drop.append(idx)
		if open_q:
			drop.extend(open_q)
		res = ''
		for idx in range(len(s)):
			if idx not in drop:
				res += s[idx]
		return res


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		stack = []
		remove = []
		for i in range(len(s)):
			if s[i] not in '()':
				continue
			elif s[i] == '(':
				stack.append(i)
			elif s[i] == ')' and (not stack):
				remove.append(i)
			else:
				stack.pop()
		stack.extend(remove)
		output = []
		for (i, v) in enumerate(s):
			if i not in stack:
				output.append(v)
		return ''.join(output)


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		if not s:
			return s
		stack = list()
		remove = list()
		for (idx, char) in enumerate(s):
			if char == '(':
				stack.append(idx)
			elif char == ')':
				if stack:
					stack.pop()
				else:
					remove.append(idx)
		remove += stack
		return ''.join([char for (idx, char) in enumerate(s) if idx not in remove])


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		to_remove = []
		stack = []
		for (i, char) in enumerate(s):
			if char == '(':
				stack.append(i)
			if char == ')':
				if not stack:
					to_remove.append(i)
				else:
					stack.pop()
		if stack:
			to_remove.extend(stack)
		output = [char for (i, char) in enumerate(s) if i not in to_remove]
		return ''.join(output)


from collections import deque

class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		toremove = []
		openP = deque()
		for i in range(len(s)):
			if s[i] == '(':
				openP.append(i)
			elif s[i] == ')':
				if len(openP) > 0:
					openP.pop()
				else:
					toremove.append(i)
		closeP = deque()
		for i in range(len(s)):
			if s[len(s) - i - 1] == ')':
				closeP.append(len(s) - i - 1)
			elif s[len(s) - i - 1] == '(':
				if len(closeP) > 0:
					closeP.pop()
				else:
					toremove.append(len(s) - i - 1)
		ret = ''
		for i in range(len(s)):
			if i not in toremove:
				ret += s[i]
		return ret


class Stack:

	def __init__(self):
		self.stack = collections.deque()

	def push(self, x):
		self.stack.append(x)

	def pop(self):
		return self.stack.pop()

	def empty(self):
		try:
			item = self.stack.pop()
			self.stack.append(item)
			return False
		except IndexError:
			return True

class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		stack = Stack()
		remove_indices = []
		for (i, char) in enumerate(s):
			if char == '(':
				stack.push(i)
			if char == ')':
				if stack.empty():
					remove_indices.append(i)
				else:
					stack.pop()
		while not stack.empty():
			remove_indices.append(stack.pop())
		res = ''
		j = 0
		for i in range(len(s)):
			if j < len(remove_indices):
				if i not in remove_indices:
					res += s[i]
				else:
					j += 1
			else:
				res += s[i]
		return res


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		ans = ''
		stack = []
		to_delete_idx = []
		for i in range(len(s)):
			if s[i] == '(':
				stack.append('(')
				to_delete_idx.append(i)
			if s[i] == ')':
				if not stack or stack[-1] == ')':
					stack.append(')')
					to_delete_idx.append(i)
				else:
					stack.pop()
					to_delete_idx.pop()
		for i in range(len(s)):
			if i not in to_delete_idx:
				ans += s[i]
		return ans


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		N = len(s)
		if N == 1 and s[0] in ('(', ')'):
			return s.replace(s[0], '')
		index = []
		stack = []
		for (i, c) in enumerate(s):
			if c == '(':
				index.append(i)
				stack.append(c)
			elif c == ')':
				if len(stack) == 0:
					index.append(i)
					stack.append(c)
				elif stack[-1] == '(':
					index.pop()
					stack.pop()
				else:
					index.append(i)
					stack.append(c)
			else:
				continue
		res = ''
		for i in range(N):
			if i not in index:
				res += s[i]
		return res


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		q = []
		ans = []
		for i in range(len(s)):
			if s[i] == '(':
				q.append(i)
			elif s[i] == ')':
				if len(q) == 0:
					ans.append(i)
				else:
					q = q[:-1]
		if len(q) != 0:
			ans = ans + q
		new_s = ''
		for i in range(len(s)):
			if not i in ans:
				new_s = new_s + s[i]
		return new_s


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		OPEN = '('
		CLOSE = ')'
		stack = []
		for (i, c) in enumerate(s):
			if c == OPEN:
				stack.append(i)
			if stack and c == CLOSE and (s[stack[-1]] == OPEN):
				stack.pop()
				continue
			if c == CLOSE:
				stack.append(i)
		output = ''
		for (i, c) in enumerate(s):
			if i not in stack:
				output += c
		return output


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		stack = []
		torem = []
		for i in range(len(s)):
			if s[i] == '(' or s[i] == '[' or s[i] == '{':
				stack.append(i)
			elif s[i] == ')':
				if len(stack) > 0 and s[stack[-1]] == '(':
					stack = stack[:-1]
				else:
					torem.append(i)
			elif s[i] == ']':
				if len(stack) > 0 and s[stack[-1]] == '[':
					stack = stack[:-1]
				else:
					torem.append(i)
			elif s[i] == '}':
				if len(stack) > 0 and s[stack[-1]] == '{':
					stack = stack[:-1]
				else:
					torem.append(i)
		stack.extend(torem)
		temp = [i for (j, i) in enumerate(list(s)) if j not in stack]
		return ''.join(temp)


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		st = []
		remove = defaultdict(int)
		for (ind, ch) in enumerate(s):
			if ch is '(':
				st.append(ind)
			elif ch is ')':
				if st:
					st.pop()
				else:
					remove[ind] += 1
		print(remove)
		if st:
			dic = {elem: 1 for elem in st}
			remove.update(dic)
		print(remove)
		ans = ''
		for (ind, ch) in enumerate(s):
			if remove[ind] == 0:
				ans += ch
		return ans


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		toRemove = []
		output = []
		for (i, c) in enumerate(s):
			if c not in '()':
				continue
			if len(toRemove) == 0:
				toRemove.append((c, i))
			elif c == ')' and toRemove[-1][0] == '(':
				toRemove.pop()
			else:
				toRemove.append((c, i))
		s_dict = {i: c for (i, c) in enumerate(s)}
		for pair in toRemove:
			del s_dict[pair[1]]
		output = [v for (k, v) in list(s_dict.items())]
		return ''.join(output)


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		new_str = ''
		left = 0
		right = 0
		for i in s:
			if i != '(' and i != ')':
				new_str += i
				continue
			if i == '(':
				left += 1
				new_str += i
				continue
			if i == ')':
				if left > 0:
					left -= 1
					new_str += i
		final_str = ''
		for i in range(len(new_str) - 1, -1, -1):
			if new_str[i] != '(' and new_str[i] != ')':
				final_str += new_str[i]
				continue
			if new_str[i] == ')':
				right += 1
				final_str += new_str[i]
				continue
			if new_str[i] == '(':
				if right > 0:
					right -= 1
					final_str += new_str[i]
		return final_str[::-1]


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		s = self.remove_invalid(s)
		s = self.remove_invalid(s[::-1], ')')
		return s[::-1]

	def remove_invalid(self, s, end='('):
		new_s = ''
		count = 0
		for i in range(len(s)):
			if s[i] not in ('(', ')'):
				new_s += s[i]
				continue
			count += 1 if s[i] == end else -1
			if count < 0:
				count = 0
			else:
				new_s += s[i]
		return new_s


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		sl = list(s)

		def sweep(begin, end, step, open_symbol, close_symbol):
			level = 0
			k = begin
			for i in range(begin, end, step):
				if sl[i] == open_symbol:
					level = max(level, 0) + 1
				elif sl[i] == close_symbol:
					level -= 1
				if not (level < 0 and sl[i] == close_symbol):
					sl[k] = sl[i]
					k += step
			return k - step
		level = 0
		r = sweep(0, len(s), 1, '(', ')')
		l = sweep(r, -1, -1, ')', '(')
		return ''.join(sl[l:r + 1])


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		paren_arr = []
		paren_stack = []
		index = 0
		for c in s:
			if c != ')' and c != '(':
				continue
			elif c == '(':
				paren_arr.append(c)
				paren_stack.append((c, index))
				index += 1
			else:
				paren_arr.append(c)
				if len(paren_stack) > 0 and paren_stack[-1][0] == '(':
					paren_stack.pop()
				else:
					paren_stack.append((c, index))
				index += 1
		for e in paren_stack:
			paren_arr[e[1]] = '-'
		s_arr = []
		index = 0
		while index < len(paren_arr) and paren_arr[index] == '-':
			index += 1
		for c in s:
			if c != ')' and c != '(':
				s_arr.append(c)
			elif index < len(paren_arr) and c == paren_arr[index]:
				s_arr.append(c)
				index += 1
				while index < len(paren_arr) and paren_arr[index] == '-':
					index += 1
		return ''.join(s_arr)


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		(l, stack) = (0, [])
		for i in s:
			if i not in '()':
				stack.append(i)
			elif i == '(':
				l += 1
				stack.append('(')
			elif l == 0:
				continue
			else:
				stack.append(')')
				l -= 1
		i = len(stack) - 1
		while l > 0 and i >= 0:
			if stack[i] == '(':
				stack[i] = ''
				l -= 1
			i -= 1
		return ''.join(stack)


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		result = []
		capacity = s.count(')')
		print(capacity)
		opened = 0
		for char in s:
			if char == '(':
				if opened == capacity:
					continue
				opened += 1
			elif char == ')':
				capacity -= 1
				if not opened:
					continue
				opened -= 1
			print(result.append(char))
			print('done')
		return ''.join(result)


class Item:

	def __init__(self, value, index):
		self.value = value
		self.index = index

class Stack:

	def __init__(self):
		self._stack = []
		self._top_index = 0

	def top(self):
		if self._top_index <= 0:
			return None
		return self._stack[self._top_index - 1]

	def pop(self):
		item = self._stack.pop()
		self._top_index -= 1
		return item

	def push(self, item):
		self._stack.append(item)
		self._top_index += 1

	def __iter__(self):
		self.index = 0
		return self

	def __next__(self):
		if self.index >= len(self._stack):
			raise StopIteration
		value = self._stack[self.index]
		self.index += 1
		return value

class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		stack = Stack()
		for (index, c) in enumerate(s):
			if c == '(':
				item = Item('(', index)
				stack.push(item)
			elif c == ')':
				if stack.top() and stack.top().value == '(':
					stack.pop()
				else:
					item = Item(')', index)
					stack.push(item)
		prev_index = 0
		result = ''
		for item in stack:
			result += s[prev_index:item.index]
			prev_index = item.index + 1
		result += s[prev_index:]
		return result


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		sum = 0
		i = 0
		ans = ''
		opens = []
		while i < len(s):
			if s[i] == '(':
				sum += 1
			elif s[i] == ')':
				sum -= 1
			if sum < 0:
				sum = 0
				i += 1
			else:
				ans += s[i]
				if ans[-1] == '(':
					opens.append(len(ans) - 1)
				i += 1
		if sum == 0:
			return ans
		while sum > 0:
			index = opens[-1]
			opens = opens[:-1]
			ans = ans[:index] + ans[index + 1:]
			sum -= 1
		return ans


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		if len(s) == 0:
			return s
		paranthesis_balance = 0
		ends = []
		for (i, char) in enumerate(s):
			if char == '(':
				paranthesis_balance += 1
			elif char == ')' and paranthesis_balance > 0:
				ends.append(i)
				paranthesis_balance -= 1
			else:
				continue
		starts = []
		paranthesis_balance = 0
		for (i, char) in enumerate(reversed(s)):
			if char == ')':
				paranthesis_balance += 1
			elif char == '(' and paranthesis_balance > 0:
				starts.append(len(s) - i - 1)
				paranthesis_balance -= 1
			else:
				continue
		balanced_str = []
		starts_i = 0
		starts = [*reversed(starts)]
		ends_i = 0
		for i in range(len(s)):
			if starts_i < len(starts) and i == starts[starts_i]:
				starts_i += 1
				balanced_str.append('(')
			elif ends_i < len(ends) and i == ends[ends_i]:
				ends_i += 1
				balanced_str.append(')')
			elif s[i] not in {'(', ')'}:
				balanced_str.append(s[i])
		return ''.join(balanced_str)


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		res = ''
		for c in s:
			if c != ')':
				res += c
			elif '(' in res:
				idx = res.rfind('(')
				res = res[:idx] + 'L' + res[idx + 1:]
				res += ')'
		res = res.replace('(', '')
		res = res.replace('L', '(')
		return res


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		to_remove = []
		stack = []
		for (i, c) in enumerate(s):
			if c == '(':
				stack.append(i)
			elif c == ')':
				if len(stack):
					stack.pop()
					continue
				to_remove.append(i)
		to_remove.extend(stack)
		s = list(s)
		for i in to_remove:
			s[i] = ''
		return ''.join(s)


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:

		def validParentheses(s, left_closed=False):
			i = 0
			res = ''
			while i < len(s):
				_i = 1
				_s = s[i]
				if _s == '(':
					(_res, __i, closed) = validParentheses(s[i + 1:], True)
					_i += __i
					if closed:
						_s += _res
					else:
						_s = _res
				elif _s == ')':
					if left_closed:
						return (res + ')', i + 1, True)
					else:
						_s = ''
				else:
					pass
				res += _s
				i += _i
			return (res, i, False)
		return validParentheses(s, False)[0]


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		par_stack = []
		for (i, ch) in enumerate(s):
			if ch == '(' or ch == ')':
				par_stack.append((i, ch))
				while len(par_stack) >= 2 and par_stack[-1][1] == ')' and (par_stack[-2][1] == '('):
					par_stack.pop()
					par_stack.pop()
		invalid = {x[0]: True for x in par_stack}
		ret = [ch for (i, ch) in enumerate(s) if i not in invalid]
		return ''.join(ret)


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		(mystack_bracket, mystack_letter) = ([], [])
		pos = 0
		for i in s:
			if i == '(':
				mystack_bracket.append((i, pos))
			elif i == ')':
				if len(mystack_bracket) != 0:
					y = mystack_bracket.pop()
					mystack_letter.append(y)
					mystack_letter.append((i, pos))
			else:
				mystack_letter.append((i, pos))
			pos += 1
		return ''.join((i for (i, j) in sorted(mystack_letter, key=lambda mystack_letter: mystack_letter[1])))


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		count = 0
		ans = ''
		for idx in range(len(s)):
			if s[idx] == '(':
				count += 1
				ans += s[idx]
			elif s[idx] == ')':
				if count > 0:
					count -= 1
					ans += s[idx]
			else:
				ans += s[idx]
		idx = len(ans) - 1
		while count > 0:
			if ans[idx] == '(':
				ans = ans[:idx] + ans[idx + 1:]
				count -= 1
			idx -= 1
		return ans


from collections import deque

class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:

		def process_s(s):
			chs = deque([])
			opening_p_count = 0
			for ch in s:
				if ch == '(':
					opening_p_count += 1
				elif ch == ')':
					if opening_p_count == 0:
						continue
					opening_p_count -= 1
				chs.append(ch)
			final_chs = deque([])
			closing_p_count = 0
			for i in range(len(chs) - 1, -1, -1):
				ch = chs[i]
				if ch == '(':
					if closing_p_count == 0:
						continue
					closing_p_count -= 1
				elif ch == ')':
					closing_p_count += 1
				final_chs.appendleft(ch)
			return ''.join(final_chs)
		return process_s(s)


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		counter = 0
		newS = ''
		for c in s:
			if c == '(':
				counter += 1
			elif c == ')':
				if counter == 0:
					continue
				counter -= 1
			newS += c
		result = ''
		for c in newS[::-1]:
			if c == '(' and counter > 0:
				counter -= 1
			else:
				result = c + result
		return result


class Solution:

	def minRemoveToMakeValid(self, s: str) -> str:
		stack = []
		left = 0
		for i in s:
			if i == '(':
				left += 1
			elif i == ')':
				if left > 0:
					left -= 1
				else:
					continue
			stack.append(i)
		if left == 0:
			return ''.join(stack)
		ans = ''
		while stack:
			val = stack.pop()
			if left > 0 and val == '(':
				left -= 1
				continue
			ans = val + ans
		return ans