Calculate the minimum number of parentheses to add to make a string valid.
A parentheses string is valid if and only if it is empty, or properly balanced. Return the minimum number of parentheses you must add to make the resulting string valid.
Input: s = "((("
Output: 3
Explanation: There are three open parentheses without any matching closing parentheses, so 3 closing parentheses must be added.

Question

Calculate the minimum number of parentheses to add to make a string valid.

A parentheses string is valid if and only if it is empty, or properly balanced. Return the minimum number of parentheses you must add to make the resulting string valid.

Input: s = "((("

Output: 3

Explanation: There are three open parentheses without any matching closing parentheses, so 3 closing parentheses must be added.

Anonymous · Accepted Answer

def min_add_to_make_valid(s: str) -> int:

open_count = 0 # unmatched '(' seen so far

added = 0 # '(' we must insert for unmatched ')'

for ch in s:

if ch == '(':

open_count += 1

elif ch == ')':

if open_count > 0:

open_count -= 1

else:

added += 1

return added + open_count

Calculate the minimum number of parentheses to add to make a string valid.

Practice this question with AI

Go Premium

Community Answers

Unlock Full Access

Practice More Questions