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.

Difficulty: interview

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:
        # ())()
        # (()
        # (()()
        # ()(()
        
        # Strategy: If sum over string at any point is negative, remove close paren immediately
        #           Keep track of open parens in string. If sum returns to 0, forget parens and restart, since this is valid so far.
        #           At the end remove (sum of string) parens from beginning.
        
        # s = lee(t(c)o)de)
        # total = 0
        # new_s = 
        # recent_opens = []
        
        total = 0
        new_s = ''
        recent_opens = []  # List of indices in new_s of open parens
        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))     

        # Remove extra open parens, if any
        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)
        
        #here, we record what parentheses need to be removed
        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)
        
        #now we remove the extra parentheses
        for char in stack:
            parentheses_index_list = data_dict[char]
            remove_char_index = parentheses_index_list.pop()
            s_list.pop(remove_char_index)
            
            #change_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:
        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
        
        print((st, st2))   
        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:
        # leftIndex, rightIndex = [],[]
        # for index, item in enumerate(s):
        #     if item == '(': leftIndex.append(index)
        #     if item == ')': rightIndex.append(index)
        # print(leftIndex,rightIndex)
        stack = []
        p = []
        for index, item in enumerate(s):
            if item == '(':
                stack.append(index)
            elif item == ')' and stack:
                p.append([stack.pop(), index])
        # s = [i for i in s.replace(')','_').replace('(','_')]
        # for [l,r] in p:
        #     s[l] = '('
        #     s[r] = ')'
        # return ''.join(s).replace('_','')
    
        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:
        # O(n) time and O(n) space - use stack to keep track of parentheses
        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)
            else:
                if 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:
        # O(n) time and O(n) space - use stack to keep track of parentheses
        stack = []
        updated_s = []
        for ch in s:
            if ch not in {'(',')'}:
                updated_s.append(ch)
            elif ch == '(':
                stack.append(len(updated_s))
                updated_s.append(ch)
            else:
                if stack:
                    updated_s.append(ch)
                    stack = stack[:-1]

        if stack:
            for i in stack[::-1]:
                updated_s = updated_s[:i] + updated_s[i+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:
                    # destroy the opening one
                    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:
        
        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])

        #at this point we should have a new string built, but it may have excessive ( at the end, so we need to check the stack

        if p_stack != []:
            #remove the items from string
            for i in p_stack:
                new_string = tmp_change(new_string, i)



            print(new_string)    

        no_zeroes=end_change(new_string)

        # print('wow')
        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
            else:
                if stack:
                    out.append(c)
                    stack = stack[:-1]
                    left_pos = left_pos[:-1]
                    l += 1
        out_string = ''
        # left_pos = set(left_pos)
        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 = []  # save indexes of parenthesis
        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)
                else:
                    if 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
#         left, right, index = 0, 0, []
#         remove_left, remove_right = 0, 0
#         for i in range(len(s)):
#             if s[i] == '(': left += 1
#             elif s[i] == ')': right += 1
#             if right > left: 
#                 remove_right += 1
#                 right -= 1
#                 index.append(i)
                
#         remove_left = left - right



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)
            
            else:
                
                if 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)
            else:
                if 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:
        # forward pass to find invalid closed paren
        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)
        # backward pass
        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 = ''
        #print (index)
        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)
            else:
                if(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('(')
            else:
                if 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):
            # find last index
            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
            else:
                if '(' 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))
                #print(\"1\", mystack_bracket)
            elif i == ')':
                if len(mystack_bracket) !=0 :
                    y = mystack_bracket.pop()
                    mystack_letter.append(y)
                    mystack_letter.append((i, pos))
                    #print(\"2:\",mystack_letter)
            else:
                mystack_letter.append((i, pos))
                #print(\"3:\",mystack_letter)
                
            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:
        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 = len(starts) - 1
        ends_i = 0
        for i in range(len(s)):
            if starts_i >= 0 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:
        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:
        counter = 0
        newS = ''
        for c in s:
            if c == ')':
                if counter > 0:
                    counter -= 1
                    newS += c
            elif c == '(':
                counter += 1
                newS += c
            else:
                newS += c
        ans = ''
        for c in newS[::-1]:
            if c == '(' and counter > 0:
                counter -= 1
            else:
                ans = c + ans
                
        
        return ans
                


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

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        c, st, st2,  res = 0, [], set(), []
        for j, ss in enumerate(s):
            if ss == '(':
                st.append(j)
            elif ss == ')':
                if st:
                    st.pop()
                else:
                    st2.add(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)