Medium

Minimum Add to Make Parentheses Valid

032

Return the minimum number of parentheses that must be added to make s valid.

EXAMPLES

Example 1

Input
{
  "s": "())"
}

Output
1

FUNCTION SHAPE

s: string→int

SOLUTION NOTE

Count unmatched '(' and unmatched ')' separately. Answer is their sum.

Reveal reference solution +

pythonREFERENCE

def minAddToMakeValid(self, s: str) -> int:
    open_count = 0
    close_needed = 0
    for c in s:
        if c == '(':
            open_count += 1
        elif open_count > 0:
            open_count -= 1
        else:
            close_needed += 1
    return open_count + close_needed

TimeO(n)

SpaceO(1)

Open on LeetCode ↗