Minimum Add to Make Parentheses Valid

Problem

Return the minimum number of parenthesis insertions needed to make s a valid parentheses string.

Track the count of unmatched openers; each unmatched closer needs one insertion, and every opener left at the end needs one closing insertion. Return 0 when s is already valid.

Hint

Every unmatched closer and every leftover opener costs exactly one insertion.

Test cases

case 1

in: ["())"]

expected: 1

case 2

in: ["((("]

expected: 3

case 3

in: ["()"]

expected: 0

case 4

in: ["()))(("]

expected: 4

case 5

in: [""]

expected: 0

Starter codePython

def min_add_parentheses(s):
    # Your code here
    pass

5 test cases · run your code against them in the editor