921. Minimum Add to Make Parentheses Valid

1. The time complexity is Θ(n²) in the worst case.

class Solution(object):
    def minAddToMakeValid(self, S):
        """
        :type S: str
        :rtype: int
        """
        
        while "()" in S:
            S = S.replace("()", "")
        
        return len(S)

2. Easy to understand

class Solution(object):
    def minAddToMakeValid(self, S):
        """
        :type S: str
        :rtype: int
        """
        stack = []
        count = 0
        for i in S:
            if i == '(':
                stack.append(i)
            elif stack:
                stack.pop()
            else:
                count += 1
        return (len(stack) + count)