921. Minimum Add to Make Parentheses Valid (Python)

Related Topic

Stack.

Description

Given a string S of ‘(‘ and ‘)’ parentheses, we add the minimum number of parentheses ( ‘(‘ or ‘)’, and in any positions ) so that the resulting parentheses string is valid.

Formally, a parentheses string is valid if and only if:

• It is the empty string, 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. Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.

Sample I/O

Example 1

Input: "())"
Output: 1

Example 2

Input: "((("
Output: 3

Example 3

Input: "()"
Output: 0

Example 4

Input: "()))(("
Output: 4

Note

1. S.length <= 1000
2. S only consists of ‘(‘ and ‘)’ characters

Methodology

This is very straight forward question. We need a stack to store temperoray characters. If stack is not empth and the top of stack is ‘(‘ and the current charceter is ‘)’ then pop top from stack. Otherwist append the character to the stack.

def minAddToMakeValid(self, S: str) -> int:
        stack = []
        for s in S:
            if stack and s==')' and stack[-1]=='(': stack.pop()
            else: stack.append(s)
        return len(stack)

BigO

We iterate the string once the time complexity is O(N).