leetcode-stack

1249. Minimum Remove to Make Valid Parentheses.py

class Solution:
    """
    Parathenses Problem --> stack + greedy
    Thought Process:
        Greedy+stack:
        We use stack to keep track of index of unmatched left parentheses.
        Top of stack is nearest index of unmatched left parenthese.
        
        We traverse the given string forward.
            when encounter the open parenthese, we append the index
            when encounter the close parenthese, 
                if stack is empty, we need to remove current close parenthese to get valid paretheses
                
                else:
                    # to balance the unmatched open parenthese
                    # use a removed_index hashset to store the index needed to be removed
                    stack.pop()
            In the end, if our stack is not empty, means we need to removed all those unmatched left parenthese, to get valid paretheses.
    (( )) )

    """
    def minRemoveToMakeValid(self, s: str) -> str:
        n = len(s)
        stack = collections.deque()
        removed_index = set()
        for i in range(n):
            char = s[i]
            if char == "(":
                stack.append(i)
            elif char == ")":
                if len(stack) != 0:
                    stack.pop()
                else:
                    # need to remove current unmatched close paretheses
                    removed_index.add(i)
        while stack:
            removed_index.add(stack.pop())
        # rebuild valid string: O(n)
        valid_str = ""
        for i, c in enumerate(s):
            if i not in removed_index:
                valid_str+=c
        return valid_str