leetcode-stack

921. Minimum Add to Make Parentheses Valid.py

class Solution:
    """
    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
                so, min_nb += 1

            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.
        while stack:
            stack.pop()
            min_nb += 1
    """
    def minAddToMakeValid(self, S: str) -> int:
        stack = collections.deque([])
        min_nb = 0
        for s in S:
            if s is '(':
                stack.append(1)
            elif s is ')':
                if len(stack) != 0:
                    stack.pop()
                else:
                    min_nb+=1
        while stack:
            stack.pop()
            min_nb+=1
        return min_nb